Go: package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"strconv"
)

const NIL = -1

type Node struct {
	id     int
	weight int
}

func init() {
	sc.Split(bufio.ScanWords)
}

type NodeHeap []Node

func (h NodeHeap) Len() int           { return len(h) }
func (h NodeHeap) Less(i, j int) bool { return h[i].weight < h[j].weight }
func (h NodeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *NodeHeap) Push(x interface{}) {
	*h = append(*h, x.(Node))
}

func (h *NodeHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	num, _ := strconv.Atoi(scanString())
	return num
}

func scanString() string {
	sc.Scan()
	return sc.Text()
}

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	n := scanInt()

	list := make([][]int, n)
	weight := make([]int, n)
	for i := range list {
		list[i] = make([]int, n)
		weight[i] = NIL
		for j := range list[i] {
			list[i][j] = NIL
		}
	}

	for i := 0; i < n; i++ {
		u := scanInt()
		k := scanInt()
		for j := 0; j < k; j++ {
			v := scanInt()
			w := scanInt()
			list[u][v] = w
		}
	}

	start := Node{id: 0, weight: 0}
	h := &NodeHeap{start}
	heap.Init(h)

	for h.Len() > 0 {
		node := heap.Pop(h).(Node)
		if weight[node.id] != NIL {
			continue
		}
		weight[node.id] = node.weight

		for i, w := range list[node.id] {
			if w == NIL {
				continue
			}
			heap.Push(h, Node{id: i, weight: w + node.weight})
		}
	}

	w := bufio.NewWriter(os.Stdout)
	for i := 0; i < n; i++ {
		fmt.Fprint(w, i)
		fmt.Fprint(w, " ")
		fmt.Fprint(w, weight[i])
		fmt.Fprintln(w)
	}
	w.Flush()
}

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()