Go: package main

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

const BIG_COST = 200000

const (
	ST_NOT_YET = iota
	ST_JOINED
)

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	nNodes := scanInt(sc)

	costs := make([][]int, nNodes)
	graph := make([][]int, nNodes)

	states := make([]int, nNodes)
	costSums := make([]int, nNodes)

	for i := 0; i < nNodes; i++ {
		costs[i] = make([]int, nNodes)
		costSums[i] = BIG_COST
	}

	for i := 0; i < nNodes; i++ {
		u := scanInt(sc)
		k := scanInt(sc)
		graph[u] = make([]int, k)
		for d := 0; d < k; d++ {
			v := scanInt(sc)
			graph[u][d] = v
			costs[u][v] = scanInt(sc)
		}
	}

	costSums[0] = 0
	for {
		minCost := BIG_COST
		var u int

		for i, cost := range costSums {
			if states[i] != ST_JOINED && cost < minCost {
				minCost = cost
				u = i
			}
		}

		if minCost == BIG_COST {
			break
		}

		states[u] = ST_JOINED

		for _, v := range graph[u] {
			cost := minCost + costs[u][v]
			if cost < costSums[v] {
				costSums[v] = cost
			}
		}
	}

	w := bufio.NewWriter(os.Stdout)
	for i, cost := range costSums {
		fmt.Fprintf(w, "%d %d\n", i, cost)
	}
	w.Flush()
}

func scanInt(sc *bufio.Scanner) int {
	sc.Scan()
	v, _ := strconv.Atoi(sc.Text())
	return v
}

Python: 
def graph_to_edges(graph):
    '''(cosr,from,to)を要素に持つリストに変換 未verify'''
    # edgeへの変換
    edges = []
    for ot, v in graph.items():
        for to, c in v:
            edges.append((c, ot, to))
    return edges

def bellman_ford(edges, s, N):
    '''
    edges ... (cost,from,to)を各要素に持つリスト
    s...始点ノード
    N...頂点数

    return
    ----------
    D ... 各点までの最短距離
    P ... 最短経路木における親
    '''
    P = [None] * N
    inf = float('inf')
    D = [inf] * N
    D[s] = 0
    for n in range(N):  # N-1回で十分だけど、N回目にもアップデートがあったらnegative loopを検出できる
        update = False  # 早期終了用
        for c, ot, to in edges:
            if D[ot] != inf and D[to] > D[ot] + c:
                update = True
                D[to] = D[ot] + c
                P[to] = ot
        if not update:
            break  # 早期終了
        if n == len(edges) - 1:
            raise ValueError('NegativeCycleError')
    return D, P

# load datas
N = int(input())
from collections import defaultdict
adj = defaultdict(lambda:[])
'''
例
[
(0について) [(1,1235), (4,65)]
(1について) [(20,6000)]
...
]
'''
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]))
            
edges=graph_to_edges(adj)


D, P = bellman_ford(edges,0,N)

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

Python: n = int(input())

adj = [[100001 for j in range(n)] for i in range(n)]

for u in range(n):
    x = list(map(int, input().split()))
    for v, c in zip(x[2::2], x[3::2]):
        adj[u][v] = c

unvisited = {v for v in range(n)}

distance = [9900001] * n


def dijkstra(s):
    distance[s] = 0

    while True:
        mincost = 9900001
        for i in unvisited:
            if distance[i] < mincost:
                mincost = distance[i]
                u = i

        if mincost == 9900001:
            break

        unvisited.discard(u)

        for v in unvisited:
            weight_uv = adj[u][v]
            if weight_uv != 100001:
                t_d = distance[u] + weight_uv
                if t_d < distance[v]:
                    distance[v] = t_d



dijkstra(0)

for v, d in enumerate(distance):
    print(v, d)

Python: INFTY = 1 << 21
WHITE = 0
GRAY = 1
BLACK = 2

def dijkstra(n, m):
    d = [INFTY] * n
    color = [WHITE] * n

    d[0] = 0
    color[0] == GRAY

    while True:
        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):
        out = d[i]
        if out == INFTY:
            out = -1
        print('{0} {1}'.format(i, out))


n = int(input())
m = [[INFTY] * n for i in range(n)]
for i in range(n):
    line = [int(v) for v in input().split()]
    u = line[0]
    k = line[1]
    for j in range(k):
        v = line[2*j + 2]
        c = line[2*j + 3]
        m[u][v] = c

dijkstra(n, m)

Python: INF = 1e9

n = int(input())
a = [[-1 for i in range(n)]for i in range(n)]
for i in range(n):
    b = list(map(int, input().split()))
    index = b[0]
    k = b[1]
    for j in range(k):
        a[index][b[2+j*2]] = b[3+j*2]


def dijkstra(s):
    flag = [0] * n
    d = [INF] * n
    d[s] = 0
    p = [-1] * n

    while True:
        min_cost = INF

        for i in range(n):
            if flag[i] != 1 and d[i] < min_cost:
                min_cost = d[i]
                u = i
        if min_cost == INF:
            break
        flag[u] = 1

        for v in range(n):
            if flag[v] != 1 and a[u][v] != -1:
                if a[u][v] + d[u] < d[v]:
                    d[v] = d[u] + a[u][v]
                    p[v] = u
    return d
d = dijkstra(0)
for i in range(n):
    print(i, d[i])

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([stack[0][0],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 range(trial):
    print(str(ans[a][0]) + " " + str(ans[a][1]))

Python: # coding: utf-8

import heapq


def dj(adjm, start):
    n = len(adjm)
    d = [float("inf")] * n
    d[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while(q):
        td, v = heapq.heappop(q)
        for k in adjm[v].keys():
            nd = td + adjm[v][k]
            if d[k] > nd:
                d[k] = nd
                heapq.heappush(q, (nd, k))
    return d


def main():
    n = int(input())
    # 隣接行列
    adjm = [{} for _ in range(n)]
    for i in range(n):
        vdata = list(map(int, input().split()))
        for j in range(vdata[1]):
            v, c = vdata[j * 2 + 2], vdata[j * 2 + 3]
            adjm[i][v] = c
    ans = dj(adjm, 0)
    for i, d in enumerate(ans):
        print(i, d)


if __name__ == "__main__":
    main()