Go: // ダイクストラのアルゴリズム
package main

import (
	"bufio"
	"fmt"
	"log"
	"math"
	"os"
	"strconv"
	"strings"
)

type color int

const (
	white color = iota // 未訪問
	mst                // MSTとして確定
)

// 頂点
type node struct {
	num     int         // 頂点の番号
	weights map[int]int // 重みMAP
	parent  *node       // MSTへの重み最小の親
	sum     int         // 始点からの距離
	color   color
}

func (p *node) getMinToMst() int {
	if p.parent == nil {
		return math.MaxInt32
	}
	return p.weights[p.parent.num]
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	n := eGetInt(scanner)

	nodes := make([]*node, n)
	for i := 0; i < n; i++ {
		weights := eAtoi((strings.Fields(eGetline(scanner))))
		v := &node{weights[0], make(map[int]int, weights[1]), nil, 0, white}
		for j := 0; j < weights[1]; j++ {
			k := weights[j*2+2] // 相手の頂点名
			w := weights[j*2+3] // 重み
			v.weights[k] = w
		}
		nodes[i] = v
	}

	// 初回はnode[0]がMSTに入るように
	nodes[0].parent = nodes[0]

	for { // 全部チェックするまで

		// どの頂点を新たにMSTに取り込むか

		var minNode *node
		min := math.MaxInt32
		for _, v := range nodes {
			if v.color == mst {
				continue
			}
			if v.getMinToMst() < min {
				min = v.getMinToMst()
				minNode = v
			}
		}
		if minNode == nil {
			// すべて完了している.
			break
		}

		// MSTに追加する頂点決定
		minNode.color = mst
		// 自分の親の合計値と合算する
		minNode.sum = minNode.parent.sum + min

		// MSTに属していない頂点それぞれについて,MSTとの最小の重みの距離を加算
		for _, v := range nodes {
			if v.color == mst {
				continue
			}
			w, ok := v.weights[minNode.num]
			if !ok {
				// minNodeと接してない
				continue
			}

			if w < v.getMinToMst() {
				// minNodeへの距離がもっとも重みが少ないので親を変更
				v.parent = minNode
			}
		}
	}

	for i, v := range nodes {
		fmt.Printf("%d %d\n", i, v.sum)
	}
}

func eGetInt(scanner *bufio.Scanner) int {
	t := eAtoi(strings.Fields(eGetline(scanner)))
	return t[0]
}

func eGetline(p *bufio.Scanner) string {
	if !p.Scan() {
		if err := p.Err(); err != nil {
			log.Fatal(err.Error())
		}
		return ""
	}
	return p.Text()
}

func eAtoi(s []string) []int {
	ints := make([]int, len(s))
	var err error
	for i, e := range s {
		ints[i], err = strconv.Atoi(e)
		if err != nil {
			log.Fatal(err.Error())
		}
	}
	return ints
}

Python: INF = 1000000


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: import sys
inf = float('inf')

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def SSSP(n, Adj):
    d = [inf] * n
    p = [-1] * n
    checked = [False] * n
    d[0] = 0
    checked[0] = True
    u = 0

    for i in range(n - 1):
        for v, cost in Adj[u]:
            if d[u] + cost < d[v]:
                p[v] = u
                d[v] = d[u] + cost

        min_n = 0
        min_w = inf
        for v in range(n):
            if not checked[v] and d[v] < min_w:
                min_n = v
                min_w = d[v]

        u = min_n
        checked[u] = True

    return d

def solve():
    n = int(input())
    Adj = [[] for i in range(n)]

    for i in range(n):
        u, k, *line = [int(i) for i in input().split()]
        for j in range(k):
            Adj[u].append((line[2*j], line[2*j + 1]))

    # debug(Adj, locals())

    d = SSSP(n, Adj)

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

if __name__ == '__main__':
    solve()

Python: import heapq

n = int(input())

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

for _ in range(n):
    tmp = list(map(int, input().split()))
    if tmp[1] != 0:
        node = tmp[0]
        for i in range(2, 2 + tmp[1] * 2, 2):
            adj[node].append((tmp[i], tmp[i + 1]))

def dijkstra(s):
    visited = [0]*n
    d = [float("inf")]*n
    
    visited[s] = 1
    d[s] = 0
    queue = [(0, s)]
    heapq.heapify(queue)
    
    while queue:
        mincost, u = heapq.heappop(queue)
        visited[u] = 2

        if d[u] >= mincost:
            for idx, i in adj[u]:
                if visited[idx] != 2 and d[idx] > d[u] + i:
                    d[idx] = d[u] + i
                    heapq.heappush(queue, (d[idx], idx))
                    visited[idx] = 1
                    
    for i in range(n):
        print(i, -1 if d[i] == float("inf") else d[i])


dijkstra(0)

Python: trial = int(input())
graph = []
for t in range(trial):
    graph.append([int(n) for n in input().split(" ")])
root = []
ans = []
stack = [[0,0]]
cnt = 0
while len(stack) > 0:
    index,out = stack[0][0],stack[0][1]
    for get in range(graph[index][1]):
        if graph[index][get*2 + 2] not in root:
            stack.append([graph[index][get*2 +2],graph[index][get*2 +3] + out ])
    if stack[0][0] not in root:
        root.append(stack[0][0])
        ans.append([str(stack[0][0]),str(stack[0][1])])
    stack.pop(0)
    stack = sorted(stack,key=lambda x:x[1])
ans = sorted(ans,key=lambda x:x[0])
for a in ans:
    print(" ".join(a))

Python: N = int(input())

#M[u][v]:隣接行列
M=[]
for n in range(N):
    input_temp=list(map(int,input().split()))
    M_temp=[-1]*N
    for k in range(0,2*input_temp[1],2):
        M_temp[input_temp[2+k]]=input_temp[2+k+1]
    M.append(M_temp)
    
#color:各頂点の訪問状態を示す
color=['white']*N

#d:TとV-Tを繋ぐ辺の中で重みが最小の辺の重みの値を保持
d=[10**10]*N

#p[v-1]:MSTにおけるvの親を保持
p=[-1]*N

#初期値
d[0] = 0
p[0] = -1

# ans=0
while True:
#     ans+=1
    mincost=10**10
    for i in range(N):
        if color[i] != 'BLACK' and d[i] < mincost:
            mincost = d[i]
            u = i
#     print(u,mincost)       
    if mincost == 10**10:
        break
    
    color[u] = 'BLACK'
    
    for v in range(N):
        if color[v] != 'BLACK' and M[u][v]!=-1:
#             print(u,v,color[v],M[u][v],d[v])
            if d[u]+M[u][v] < d[v]:
                d[v] = d[u] + M[u][v]
                p[v] = u
                color[v] = 'GRAY'
    # print(color,mincost,d,p)
    
for d_ in enumerate(d):
    print(d_[0],d_[1])

Python: N=int(input())
rinsetu=[[1000000 for i in range(N)] for j in range(N)]
d=[1000000]*(N)
color=["white"]*N
for i in range(N):
    a=list(map(int,input().split()))
    for j in range(a[1]):
        j1=j*2+2
        j2=j*2+3
        rinsetu[i][a[j1]]=a[j2]
def hunterhunter():
    d[0]=0
    while(True):
        mincost=1000000
        for i in range(N):
            if color[i]=="white" and mincost>d[i]:
                mincost=d[i]
                u=i
        if mincost==1000000:break
        color[u]="black"
        for i in range(N):
            if color[i]=="white" and rinsetu[u][i]!=1000000:
                if rinsetu[u][i]+d[u]<d[i]:
                    d[i]=rinsetu[u][i]+d[u]
hunterhunter()
for i,cost in enumerate(d):
    print(i,cost)