Go: package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const (
	white int = iota
	gray
	black
)

type node struct {
	id     int
	parent int
	edge   []int
	weight []int
	color  int
}

type graph struct {
	nodes    []node
	distance []int
}

var infty = 1 << 32
var null = -1

func constructgraph() *graph {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	n := nextInt(sc)

	g := &graph{make([]node, n), make([]int, n)}

	for i := 0; i < n; i++ {
		id := nextInt(sc)
		edges := nextInt(sc)
		n := node{}
		n.id = id
		n.edge = make([]int, edges)
		n.weight = make([]int, edges)
		n.color = white
		for j := 0; j < edges; j++ {
			to := nextInt(sc)
			w := nextInt(sc)
			n.edge[j] = to
			n.weight[j] = w
		}
		g.nodes[id] = n
	}
	return g
}

func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	v, _ := strconv.Atoi(sc.Text())
	return v
}

func (g *graph) preparedijkstra(s int) {
	for i := 0; i < len(g.nodes); i++ {
		g.nodes[i].color = white
		g.nodes[i].parent = null
		g.distance[i] = infty
	}
	g.distance[s] = 0
}

func (g *graph) dijkstra(s int) []int {
	g.preparedijkstra(s)

	for {
		var u int
		mincost := infty
		for i, d := range g.distance {
			if g.nodes[i].color != black && mincost > d {
				mincost = d
				u = i
			}
		}

		if mincost == infty {
			break
		}

		g.nodes[u].color = black

		for i, e := range g.nodes[u].edge {
			if g.nodes[e].color != black {
				if g.distance[e] > g.distance[u]+g.nodes[u].weight[i] {
					g.distance[e] = g.distance[u] + g.nodes[u].weight[i]
					g.nodes[e].parent = u
					g.nodes[e].color = gray
				}
			}
		}
	}
	return g.distance
}

func printShortestPath(d []int) {
	for i, v := range d {
		fmt.Printf("%d %d\n", i, v)
	}
}

func main() {
	g := constructgraph()
	d := g.dijkstra(0)
	printShortestPath(d)
}

Python: from collections import namedtuple

Edge = namedtuple('Edge', ('fr', 'to', 'cost'))
inf = 1e9


def bf(n, s, es):
    d = [inf for _ in range(n)]
    d[s] = 0
    while True:
        updated = False
        for e in es:
            if d[e.fr] != inf and d[e.fr] + e.cost < d[e.to]:
                updated = True
                d[e.to] = d[e.fr] + e.cost

        if not updated:
            break

    return d


n = int(input())

m = [[-1 for _ in range(n)] for _ in range(n)]
es = []
for i in range(n):
    fs = list(map(int, input().split()))
    ne = fs[1]
    for j in range(ne):
        v = fs[2+2*j]
        c = fs[2+2*j+1]
        m[i][v] = c
        es.append(Edge(i, v, c))


d = bf(n, 0, es)
for (i, di) in enumerate(d):
    print(i, di)

Python: # coding: utf-8

import heapq


class Dijkstra:

    """
    Dijkstra's algorithm: find the shortest path from a vertex
    Complexity: O(E + log(V))
    used in GRL1A(AOJ)
    """

    def __init__(self, V, G, INF=float("inf")):

        """
        V: the number of vertexes
        E: adjacency list (all edge in G must be 0 or positive)
        INF: Infinity distance
        """
        self.V = V
        self.G = G
        self.INF = INF
        self.distance, self.prev = list(), list()


    def dijkstra(self, start):

        Q = list()
        self.distance = [self.INF for _ in range(self.V)]
        self.prev = [-1 for _ in range(self.V)]

        self.distance[start] = 0
        heapq.heappush(Q, (0, start))

        while len(Q) > 0:
            dist, from_v = heapq.heappop(Q)
            if self.distance[from_v] < dist:
                continue
            for to_v, nxt_dist in self.G[from_v]:
                if self.distance[from_v] + nxt_dist >= self.distance[to_v]:
                    continue
                self.distance[to_v] = self.distance[from_v] + nxt_dist
                heapq.heappush(Q, (self.distance[to_v], to_v))
                self.prev[to_v] = from_v
        
        return self.distance


    def get_path(self, goal):

        path = [goal]
        while self.prev[goal] != -1:
            path.append(prev[goal])
            goal = self.prev[end]

        return path[::-1]


if __name__ == "__main__":
    
    n = int(input())
    g = [[] for _ in range(n)]
    for _ in range(n):
        v, _, *e = map(int, input().split())
        for u, d in zip(e[::2], e[1::2]):
            g[v].append((u, d))

    dist = Dijkstra(n, g).dijkstra(0)
    for i, d in enumerate(dist):
        print(i, d)

Python: from enum import Enum


class Sssp(object):
    """ single source shortest path """
    INFINITY = 999999999
    class Status(Enum):
        """ ?????????????¨??????¶??? """
        white = 1  # ????¨????
        gray = 2  # ?¨???????
        black = 3  #?¨???????

    def __init__(self, data):
        num_of_nodes = len(data)
        self.color = [Sssp.Status.white] * num_of_nodes  # ????????????????¨??????¶???
        self.M = [[Sssp.INFINITY] * num_of_nodes for _ in range(num_of_nodes)]
        self._make_matrix(data)  # data????????????????????£??\??????(?????\?¶???¨???????????????????????§????????????)
        self.d = [Sssp.INFINITY] * num_of_nodes
        self.p = [-1] * num_of_nodes  # ????????????????????????????¨??????????

    def _make_matrix(self, data):
        for d in data:
            my_id = d[0]
            d = d[2:]
            while len(d) > 1:
                to_node, cost = d[0], d[1]
                self.M[my_id][to_node] = cost
                d = d[2:]

    def dijkstra(self, start):
        self.d[start] = 0
        self.p[start] = -1

        while True:
            mincost = Sssp.INFINITY
            for i in range(len(self.d)):
                if self.color[i] != Sssp.Status.black and self.d[i] < mincost:
                    mincost = self.d[i]
                    u = i

            if mincost == Sssp.INFINITY:
                break

            self.color[u] = Sssp.Status.black

            for v in range(len(self.d)):
                if self.color[v] != Sssp.Status.black and self.M[u][v] != Sssp.INFINITY:
                    if self.d[u] + self.M[u][v] < self.d[v]:
                        self.d[v] = self.d[u] + self.M[u][v]
                        self.p[v] = u
                        self.color[v] = Sssp.Status.gray


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())
    data = []
    for i in range(num):
        data.append(list(map(int, input().split(' '))))

    # ???????????¢?´¢
    s = Sssp(data)
    s.dijkstra(0)

    # ???????????¨???
    for i in range(num):
        print('{0} {1}'.format(i, s.d[i]))

Python: n=int(input())
inf=10**15;d=[inf]*n;d[0]=0
node=[[]for _ in range(n)]
for i in range(n):
	x=list(map(int,input().split()))
	for j in range(x[1]):
		node[i].append((x[j*2+2],x[j*2+3]))
dis=[[inf]*n for _ in range(n)]
for i in range(n):
	dis[i][i]=0
for i in range(n):
	for x in node[i]:
		dis[i][x[0]]=x[1]
s=[False]*n
while True:
	min_cost=inf
	for i in range(n):
		if s[i]==0 and d[i]<min_cost:
			min_cost=d[i]
			u=i
	if min_cost==inf:
		break
	s[u]=True
	for i in range(n):
		if s[i]==False and dis[u][i]!=inf:
			if d[u]+dis[u][i]<d[i]:
				d[i]=d[u]+dis[u][i]		
for i in range(n):
	print(i,d[i])

Python: n = int(input())
from collections import defaultdict
G = defaultdict(list)
for i in range(n):
    i = [int(i) for i in input().split()]
    k = i[1]
    G[i[0]] = list(zip(i[2::2],i[3::2]))

def mind(Q, d):
    c = float('inf')
    ret = 0
    for i, j in enumerate(d):
        if c > j and i in Q:
            c = j
            ret = i
    return ret

def dijkstra(G):
    d = [0] + [float('inf')] * (n - 1)
    Q = set(range(n))
    while len(Q) != 0:
        u = mind(Q, d)
        print(u)
        Q = Q - set([u])
        for v, c in G[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
    return d

for i,j in enumerate(dijkstra(G)):
    print(i, j)