Go: package main

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

func main() {
	r := bufio.NewReader(os.Stdin)

	var n int
	fmt.Fscan(r, &n)
	cs := make([]map[int]int, n) // []v_i -> c_i
	for h := 0; h < n; h++ {
		var u, k int
		fmt.Fscan(r, &u, &k)
		m := make(map[int]int)
		for i := 0; i < k; i++ {
			var v, c int
			fmt.Fscan(r, &v, &c)
			m[v] = c
		}

		cs[u] = m
	}

	q := make(map[int]int)
	q[0] = 0
	visited := make(map[int]struct{})
	out := make([]int, n)

	for len(q) > 0 {
		u := top(q)
		for uu, c := range cs[u] {
			// Consider the connection between u and uu.
			if _, ok := visited[uu]; ok {
				continue
			}
			if d, ok := q[uu]; !ok || d > q[u]+c {
				q[uu] = q[u] + c
			}
		}

		out[u] = q[u]
		delete(q, u)
		visited[u] = struct{}{}
	}

	for u, d := range out {
		fmt.Println(u, d)
	}
}

func top(q map[int]int) int {
	minu := -1
	min := -1
	for u, d := range q {
		if min < 0 || d < min {
			minu = u
			min = d
		}
	}

	return minu
}

Python: import sys

def dijkstra(v_count: int, edges: list, start: int,
             *, adj_matrix: bool = False, unreachable=float("inf")) -> list:
    """ ダイクストラ法
    :param v_count: 頂点数
    :param edges: 辺のリスト(隣接リストor隣接行列)
    :param start: スタートする頂点
    :param adj_matrix: edgesに渡したリストが隣接行列ならTrue
    :param unreachable: 到達不能を表すコスト値
                        隣接行列の辺の有無の判定および返すリストの初期値に使用
    """
    from heapq import heappush, heappop

    vertices = [unreachable] * v_count
    vertices[start] = 0
    q, rem = [(0, start)], v_count - 1

    while q and rem:
        cost, v = heappop(q)
        if vertices[v] < cost:
            continue
        rem -= 1

        dests = (filter(lambda x: x[1] != unreachable, enumerate(edges[v]))
                 if adj_matrix else edges[v])

        print(list(dests))
        for dest, _cost in dests:
            newcost = cost + _cost
            if vertices[dest] > newcost:
                vertices[dest] = newcost
                heappush(q, (newcost, dest))

    return vertices

n = int(input())
edges = [[] for _ in [0]*n]
for a in (tuple(map(int, l.split())) for l in sys.stdin):
    edges[a[0]] = tuple(zip(a[2::2], a[3::2]))
vertices = dijkstra(n, edges, 0)
for i, n in enumerate(vertices):
    print(i, n)

Python: INF = 1e9

n = int(input())
adj_matrix = [[INF for i in range(n)] for j in range(n)]

for i in range(n):
    u, k, *line = list(map(int, input().split()))
    #print(u,k, line)
    for j in range(k):
        adj_matrix[u][line[2*j]] = line[2*j+1]
        adj_matrix[line[2*j]][u] = line[2*j+1]

def dijkstra(x):
    isVisited = [False] * x
    d = [INF] * x #????????????????????????????????¢????????????????°?????????????????´????ex d[i] = 6 ?????????????????????i????????????????????????????????????????????????????°?????????¢???6
    d[0] = 0
    p = [-1] * x # MST??????????????????i???????????¨??????ex p = [-1,0,3,0,2]??¨????????¨?????????0???????????????????????????????????¨??\?¶??????????2?????????3??¨??\?¶????
    
    while True:
        min_cost = INF
        
        for i in range(x):
            if isVisited[i] != True and d[i] < min_cost:
                min_cost = d[i]
                u = i
        
        if min_cost == INF:
            break
        
        isVisited[u] = True
        
        for v in range(x):
            if isVisited[v] != True and adj_matrix[u][v] != -1:
                if d[u] + adj_matrix[u][v] < d[v]:
                    d[v] = d[u] + adj_matrix[u][v]
                    p[v] = u
    return d

for i, di in enumerate(dijkstra(n)):
    print(i, di)

Python: INF = float("inf")
white = 0; gray = 1; black =2

def dijkstra(s):
    # 頂点sをrootに設定
    mindist[s] = 0 

    while True:
        #最短経路木に頂点(最短経路木とつながる最小コストの辺を持つ頂点)を追加
        mincost = INF
        u = -1
        for i in range(n):
            if color[i] != black and mindist[i] < mincost:
                mincost = mindist[i]
                u = i
        if u == -1: break
        color[u] = black
        # 各頂点についてsからの最小コストを更新
        for v in range(n):
            if color[v] == black: continue # 確定済み
            if M[u][v] == INF: continue # 2頂点の間に辺が存在しない
            if mindist[u] + M[u][v] < mindist[v]:
                mindist[v] = mindist[u] + M[u][v]
                color[v] = gray

if __name__ == "__main__":
    n = int(input())
    M = [[INF]*n for _ in range(n)]
    for i in range(n):
        inp = [int(x) for x in input().split()]
        u = inp[0]
        k = inp[1]
        for v,c in zip(inp[2::2],inp[3::2]): M[u][v] = c
    color = [white]*n #各頂点の訪問状態 （white:未訪問 gray:暫定 black:確定）
    mindist = [INF]*n # 始点sからの最小コスト
    dijkstra(0)
    for i in range(n): print("{} {}".format(i,mindist[i]))

Python: N = int(input())
INF = 10**9

M = [[-1 for i in range(N)] for j in range(N)]
for i in range(N):
  u, k, *vs = list(map(int, input().split()))
  for j in range(k):
    v, c = vs[2*j], vs[2*j+1]
    M[u][v] = c

d = [INF for i in range(N)]
d[0] = 0
p = [-1 for i in range(N)]
mst = [False for i in range(N)]

while True:
  min_w = INF
  for i in range(N):
    if not mst[i] and d[i] < min_w:
      min_w = d[i]
      u = i
  if min_w == INF:
    break
  mst[u] = True
  for v in range(N):
    if M[u][v] != -1 and M[u][v] + d[u] < d[v]:
      d[v] = M[u][v] + d[u]
      p[v] = u

for i in range(N):
  print(i, d[i])

Python: #!/usr/bin/python3
n = int(input())
inf = 100 * 100000

M = [[inf for i in range(n)] for j in range(n)]

for i in range(n):
    L = list(map(int, input().split()))
    u = L[0]
    k = L[1]
    v = L[2::2]
    c = L[3::2]
    for j in range(k):
        M[u][v[j]] = c[j]

S = set()
V = set(range(n))
S.add(0)
d = [inf for i in range(n)]
d[0] = 0
count = 0
while len(V - S) != 0:
    T = V - S
    nd = [inf for i in range(n)]
    for s in S:
        for m, c in enumerate(M[s]):
            if d[s] + c < nd[m] and m in T:
                nd[m] = d[s] + c

    min_nd = min(nd)
    u = nd.index(min_nd)
    S.add(u)
    d[u] = min_nd


for i, v in enumerate(d):
    print(i, v)

Python: INFTY = 1 << 21
WHITE = 0
GRAY = 1
BLACK = 2
 
n = int(input())
M = [list(map(int, input().split())) for i in range(n)]
 
d = [INFTY for i in range(n)]
color = [WHITE for i in range(n)]
 
for u in range(n):
    U = list(map(int, input().split()[2:]))
    for j in range(0, len(U), 2):
        M[u][U[j]] = U[j + 1]
        
def dijkstra():
    global M, d, color
    d[0] = 0
    color[0] = GRAY
    while(1):
        minv = INFTY
        u = -1
        for i in range(n):
            if (minv > d[i] and color[i] != BLACK):
                u = i
                minv = d[i]
        if (u == -1):
            break
        color[u] = BLACK
        for v in range(n):
            if (color[v] != BLACK and M[u][v] != INFTY):
                if (d[v] > d[u] + M[u][v]):
                    d[v] = d[u] + M[u][v]
                    color[v] = GRAY
    for i in range(n):
        print(str(i), (-1 if d[i] == INFTY else str(d[i])))
dijkstra()

Python: def V_dijkstra(V,AL,S):
    INF=float('inf')
    ans=[INF]*V
    ans[S]=0
    used=[0]*V # 0:未確定
    used[S]=1
    que=[i for i in range(V)]
    while que:
        u=min(que,key=lambda x: ans[x])
        que.pop(que.index(u))
        used[u]=1
        for v,w in AL[u]:
            if not used[v] and ans[v]>ans[u]+w:
                ans[v]=ans[u]+w
    return ans

# verified: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_B
N=int(input())
AL=[[] for _ in range(N)]
for _ in range(N):
    for i,x in enumerate(input().split()):
        x=int(x)
        if i==0:
            j=x
        elif i==1:
            pass
        else:
            if i%2==0:
                tmp=[x]
            else:
                tmp.append(x)
                AL[j].append(tmp)
for ans in enumerate(V_dijkstra(N,AL,0)):
    print(*ans)