Go: package main

import (
	"bufio"
	"bytes"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
)

const (
	INFTY = 1 << 21
	NIL   = -1
)

const (
	WHITE = iota
	GRAY
	BLACK
)

type Graph [][]int

func (g *Graph) dikstra(n int) string {
	var (
		u, minv = 0, 0
	)

	d := make([]int, n)
	color := make([]int, n)

	for i := 0; i < n; i++ {
		d[i] = INFTY
		color[i] = WHITE
	}
	d[0] = 0
	color[0] = GRAY

	for {
		minv = INFTY
		u = -1
		for i := 0; i < n; i++ {
			if minv > d[i] && color[i] != BLACK {
				u = i
				minv = d[i]
			}
		}

		if u == -1 {
			break
		}

		color[u] = BLACK
		for v := 0; v < n; v++ {
			if color[v] != BLACK && (*g)[u][v] != INFTY {
				if d[v] > d[u]+(*g)[u][v] {
					d[v] = d[u] + (*g)[u][v]
					color[v] = GRAY
				}
			}
		}
	}

	var out bytes.Buffer
	for i := 0; i < n; i++ {
		out.WriteString(fmt.Sprintf("%d ", i))
		if d[i] == INFTY {
			out.WriteString(fmt.Sprintf("%d\n", -1))
			continue
		}
		out.WriteString(fmt.Sprintf("%d\n", d[i]))
	}

	return strings.TrimRight(out.String(), "\n")
}

func answer(reader io.Reader) string {
	sc := bufio.NewScanner(reader)
	sc.Split(bufio.ScanWords)

	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())

	g := make(Graph, n)
	for i := 0; i < n; i++ {
		g[i] = make([]int, n)
		for j := 0; j < n; j++ {
			g[i][j] = INFTY
		}
	}

	for i := 0; i < n; i++ {
		sc.Scan()
		u, _ := strconv.Atoi(sc.Text())
		sc.Scan()
		k, _ := strconv.Atoi(sc.Text())

		for j := 0; j < k; j++ {
			sc.Scan()
			v, _ := strconv.Atoi(sc.Text())
			sc.Scan()
			c, _ := strconv.Atoi(sc.Text())

			g[u][v] = c
		}
	}

	return g.dikstra(n)
}

func main() {
	fmt.Println(answer(os.Stdin))
}

Python: def diikstraMethd(G, s):
    # ?????????
    n = len(G)
    # White:0 Gyay:1 Black:2
    color = [0 for _ in range(n)]
    d = [INF for _ in range(n)]
    p = [None for _ in range(n)]

    d[s] = 0

    while True:
        mincost = INF
        for i in range(n):
            if color[i] != 2 and d[i] < mincost:
                mincost = d[i]
                u = i

        if mincost == INF: break

        color[u] = 2

        for v in range(n):
            if color[v] != 2 and M[u][v] != INF:
                if d[u] + M[u][v] < d[v]:
                    d[v] = d[u] + M[u][v]
                    p[v] = u
                    color[u] = 1

    return d

if __name__ == '__main__':
    n = int(input())
    M = [[INF for _ in range(n)] for i in range(n)]
    for _ in range(n):
        tmp = list(map(int, input().split()))
        u = tmp.pop(0)
        k = tmp.pop(0)
        for _ in range(k):
            v = tmp.pop(0)
            c = tmp.pop(0)
            M[u][v] = c
    d = diikstraMethd(M, 0)


    for i in range(n):
        print('{0} {1}'.format(i, d[i]))

Python: n = int(input())
adjc_list = [[] for _ in range(n)]
INF = 99999999999999999999
V = [ele for ele in range(n)]
S = []
d = [INF] * n
p = [ele for ele in range(n)]

for i in range(n):
    tmp = [int(ele) for ele in input().split()]
    for j in range(1, tmp[1]*2, 2):
        v = tmp[j+1]
        w = tmp[j+2]
        adjc_list[i].append([w, v])
    adjc_list[i].sort()


def my_dijkstra_solver():
    root = 0  # given
    # 1. 初期化
    d = [INF] * n
    d[root] = 0
    VS = V

    # 2. 以下の処理を、S = Vになるまで繰り返す
    while VS:
        # 2.1. V-S の中から、 d[u] が最小である頂点 u を選択する。
        u = VS[0]
        for i in VS:
            if d[i] < d[u]:
                u = i

        S.append(u)  # 2.2. u を S に追加する.

        # 2.3. u に隣接し, かつ V-S に属するすべての頂点 v に対する以下の値を更新する
        VS.remove(u)
        for w, v in adjc_list[u]:
            if v in VS:
                if d[u] + w < d[v]:
                    d[v] = d[u] + w
                    p[v] = u  # 親をどこかで使うのはわかるが一旦忘れよう

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


if __name__ == "__main__":
    my_dijkstra_solver()

Python: from sys import stdin
input = stdin.readline

infty = 100_000_00

def dijkstra(N):
    d[0] = 0
    p[0] = -1
    u = 0

    while True:
        mincost = infty
        for i in range(N):
            if color[i] != 2 and d[i] < mincost:
                mincost = d[i]
                u = i
        color[u] = 2
        if mincost == infty:
            break

        for v in range(N):
            if M[u][v] != infty and color[v] != 2 :
                if M[u][v] + d[u] < d[v]:
                    d[v] = M[u][v] + d[u]
                    p[v] = u
                    color[v] = 1

N = int(input())
M = [[infty] * N for i in range(N)]
d = [infty] * N #V-T間の重み最小辺の記録
p = [-1] * (N)
color = [0] * N

for i in range(N):
    a = list(map(int, input().split()))
    for k in range(1, len(a)//2):
        M[i][a[2*k]] = a[2*k+1]


dijkstra(N)

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

Python: import heapq

n = int(input())
d = [float("inf") for i in range(n)]
d[0] = 0
g = []
q = []

for i in range(n):
    heapq.heappush(q, (d[i], i))
    inp = list(map(int, input().split()))
    tmp = []
    for j in range(inp[1]):
        tmp.append(inp[2*j+2:2*j+4])
    g.append(tmp)

while q:
    q_pop = heapq.heappop(q)
    i = q_pop[1]
    if q_pop[0] > 100*100000:
        continue
    for node in g[i]:
        d_tmp = d[i] + node[1]
        if d_tmp < d[node[0]]:
            d[node[0]] = d_tmp
            heapq.heappush(q, (d_tmp, node[0]))

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

Python: from sys import stdin
from collections import deque

def read_graph(n):
    A = [ [-1]*(n+1) for _ in range(n+1) ]
    for _ in range(n):
        line = deque(stdin.readline().strip().split())
        u = line.popleft()
        line.popleft()
        for l, k in enumerate(line):
            if l % 2 == 0:
                v = k
            else:
                A[int(u)][int(v)] = int(k)
    return A

def dijkstra(n, A, s):
    color = [ 'WHITE' for i in range(n) ]
    d = [ float('inf') for i in range(n) ]
    d[s] = 0
    p = [-1] * n

    while True:
        mincost = float('inf')
        for i in range(n):
            if color[i] != 'BLACK' and d[i] < mincost:
                mincost = d[i]
                u = i

        if mincost == float('inf'):
            break

        color[u] = 'BLACK'

        for v in range(n):
            if color[v] != 'BLACK' and A[u][v] != -1:
                if d[u] + A[u][v] < d[v]:
                    d[v] = d[u] + A[u][v]
                    p[v] = u
                    color[v] = 'GRAY'

    return d

n = int(input())
A = read_graph(n)
for i, k in enumerate(dijkstra(n, A, 0)):
    print(i, k)

Python: import sys
import heapq
input=sys.stdin.readline
INF=2<<28

def dijkstra(G,start,n):#グラフ,初期頂点,頂点数

    dist=[INF]*n;dist[start]=0
    used=[False]*n;used[0]=True
    q=[]

    for v in G[start]:
        heapq.heappush(q,v)
    
    while len(q)>0:
        now=heapq.heappop(q)
        if used[now[1]]:
            continue
        v=now[1]
        dist[v]=now[0]
        used[v]=True

        for e in G[v]:
            if not used[e[1]]:
                heapq.heappush(q,(e[0]+dist[v],e[1]))

    return dist

N=int(input().rstrip())
g=[[] for _ in range(N)]
for _ in range(N):
    u,k,*c=map(int,input().split())
    for j in range(0,k*2,2):
        g[u].append((c[j+1],c[j]))

ans=dijkstra(g,0,N)
for i,x in enumerate(ans):
    print(i,x)