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

Python: def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N):
        u, k, *vc = (int(i) for i in input().split())
        for i in range(0, len(vc), 2):
            G[u].append((vc[i], vc[i+1]))
    d = [[(1 << 63)-1, i] for i in range(N)]
    from heapq import heapify, heappop, heappush

    def dijkstra(s):
        d[s][0] = 0
        que = [(d[s][0], s)]
        heapify(que)
        finished = set()
        while len(finished) < N:
            u = heappop(que)
            while u[1] in finished:
                u = heappop(que)
            for v, c in G[u[1]]:
                if v in finished:
                    continue
                if d[v][0] > u[0] + c:
                    d[v][0] = u[0] + c
                    heappush(que, (d[v][0], v))
            finished.add(u[1])
    dijkstra(0)
    for i, val in enumerate(d):
        print(i, val[0])


if __name__ == '__main__':
    main()

Python: # -*- coding: utf-8 -*-
"""
Created on Sat Jul 14 19:11:44 2018

@author: maezawa
"""
infinity = 2*10**9

n = int(input())
adj = [[] for _ in range(n)]

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

color = [0]*n
d = [infinity for _ in range(n)]
p = [0]*n
p[0] = -1
d[0] = 0

def dyk(s):
    cnt = 1
    cur = s
    candidates = set() # remaining nodes
    while True:
        for i, w in adj[cur]:
            if color[i] == 2:
                continue
            if d[i] > d[cur] + w:
                d[i] = d[cur] + w
                color[i] = 1
            candidates.add(i)
        min_d = infinity
        for j in candidates:
            if min_d > d[j]:
                min_node = j
                min_d = d[j]
        candidates.remove(min_node)
        p[min_node] = cur
        color[cur] = 2
        cur = min_node
        cnt += 1
        print(cur, d)
        print(candidates)
        if cnt == n:
            break
    return

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

Python: import sys
import math

n = int(sys.stdin.readline())

Q = set()
out_edge = [set() for _ in range(n)]
weight = [[0] * n for _ in range(n)]

for _ in range(n):
    ll = list(map(int, sys.stdin.readline().split()))
    sn = ll[0]
    Q.add(sn)
    for j in range(ll[1]):
        en = ll[2+2*j]
        cn = ll[2+2*j+1]
        out_edge[sn].add(en)
        weight[sn][en] = cn

d = [0] + [math.inf for _ in range(n-1)]
prev = [None] * n

while len(Q)>0:
    minval = math.inf
    u = -1
    for q in Q:
        if minval > d[q]:
            minval = d[q]
            u = q
    if minval==math.inf:  break
    Q.remove(u)

    for v in out_edge[u]:
        if weight[u][v]>0:
            if d[v] > d[u] + weight[u][v]:
                d[v] = d[u] + weight[u][v]
                prev[v] = u

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

Python: from sys import stdin
INF = 1<<21
WHITE, GRAY, BLACK = 0, 1, 2
n = int(stdin.readline())
M = [[INF] * n for _ in range(n)]
for u in range(0, n):
    U = list(map(int, stdin.readline().split()[2:]))
    for j in range(0, len(U), 2):
        M[u][U[j]] = U[j + 1]
d = [INF] * n
d[0] = 0
color = [WHITE] * n
color[0] = GRAY
def dijkstra():
    global n
    while True:
        minv = INF
        u = -1
        for i in range(0, 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(0, n):
            if color[v] != BLACK and M[u][v] != INF and d[v] > d[u] + M[u][v]:
                d[v] = d[u] + M[u][v]
                color[v] = GRAY
    for i in range(0, n):
        print(i, (-1 if d[i] == INF else d[i]))
dijkstra()

Python: 
n=int(input())
graph=[[0]*n for i in range(n)]


#graph[i][j]は、頂点iから頂点jへの枝の重みを表す(0は枝なし)
for loop in range(n):
    tmp_ope=list(map(int,input().split()))
    for j in range(1,tmp_ope[1]+1):
        graph[tmp_ope[0]][tmp_ope[2*j]]=tmp_ope[2*j+1]

#S[i]＝１の時、頂点iは走査済み
S=[0]*n
#d[i]はSに含まれる点のみを使って、頂点iにたどり着くときの最短パス
d=[999999]*n
d[0]=0

for loop in range(n):
    tmp_vertex=-1

    #tmp_vertexは走査済みでない点の中で、d[i]が最小となるインデックス
    for j in range(n):
        if(S[j]==0):
            if(tmp_vertex!=-1):
                if(d[j] < d[tmp_vertex]):
                    tmp_vertex=j
            else:
                tmp_vertex=j
    
    
    S[tmp_vertex]=1

    #dを更新
    for j in range(n):
        if(graph[tmp_vertex][j]!=0 and S[j]==0):
            d[j]=min([ d[j], d[tmp_vertex] + graph[tmp_vertex][j] ])

for i in range(n):
    print(f"{i} {d[i]}")