Go: package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)

	g := makeGraph(n)
	for i := 0; i < n; i++ {
		u := getNextInt(scanner)
		k := getNextInt(scanner)
		for ii := 0; ii < k; ii++ {
			v := getNextInt(scanner)
			c := getNextInt(scanner)
			g[u][v] = c
		}
	}

	ans := make([]int, n)
	im := make(IntMap, 1)
	im.increment(0)
	for len(im) < n {
		min := 1 << 30
		x := -1
		for u := range im {
			for v := 0; v < n; v++ {
				if im.get(v) != 0 {
					continue
				}
				if min > ans[u]+g[u][v] {
					min = ans[u] + g[u][v]
					x = v
				}
			}
		}
		im.increment(x)
		ans[x] = min
	}

	for i := 0; i < n; i++ {
		fmt.Fprintln(writer, fmt.Sprintf("%d %d", i, ans[i]))
	}
	writer.Flush()
}

func makeGraph(n int) [][]int {
	g := make([][]int, n)
	for i := 0; i < n; i++ {
		g[i] = make([]int, n)
		for ii := 0; ii < n; ii++ {
			g[i][ii] = 1 << 30
		}
	}

	return g
}

// IntMap ...
type IntMap map[int]int

func (m IntMap) get(key int) int {
	if _, ok := m[key]; ok {
		return m[key]
	}
	return 0
}
func (m IntMap) increment(key int) {
	if _, ok := m[key]; ok == false {
		m[key] = 0
	}
	m[key]++
}

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)