Go: package main

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

func main() {
	r := bufio.NewReader(os.Stdin)

	var n int
	fmt.Fscan(r, &n)
	cs := make([]map[int]int, n) // []v_i -> c_i
	for h := 0; h < n; h++ {
		var u, k int
		fmt.Fscan(r, &u, &k)
		m := make(map[int]int)
		for i := 0; i < k; i++ {
			var v, c int
			fmt.Fscan(r, &v, &c)
			m[v] = c
		}

		cs[u] = m
	}

	q := make(map[int]int)
	q[0] = 0
	visited := make(map[int]struct{})
	out := make([]int, n)

	for len(q) > 0 {
		u := top(q)
		for uu, c := range cs[u] {
			// Consider the connection between u and uu.
			if _, ok := visited[uu]; ok {
				continue
			}
			if d, ok := q[uu]; !ok || d > q[u]+c {
				q[uu] = q[u] + c
			}
		}

		out[u] = q[u]
		delete(q, u)
		visited[u] = struct{}{}
	}

	for u, d := range out {
		fmt.Println(u, d)
	}
}

func top(q map[int]int) int {
	minu := -1
	min := -1
	for u, d := range q {
		if min < 0 || d < min {
			minu = u
			min = d
		}
	}

	return minu
}

Python: #!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
5
0 3 2 3 3 1 1 2
1 2 0 2 3 4
2 3 0 3 3 1 4 1
3 4 2 1 0 1 1 4 4 3
4 2 2 1 3 3

output:
0 0
1 2
2 2
3 1
4 3
"""

import sys
import heapq as hp

WHITE, GRAY, BLACK = 0, 1, 2
D_MAX = int(1e7 + 1)


def generate_adj_matrix(v_info):
    for v_detail in v_info:
        v_index = int(v_detail[0])
        v_adj_length = int(v_detail[1])
        v_adj_list = v_detail[2:]
        # assert len(v_adj_list) == v_adj_length * 2
        for j in range(0, v_adj_length * 2, 2):
            init_adj_matrix[v_index][v_adj_list[j]] = int(v_adj_list[j + 1])

    return init_adj_matrix


def dijkstra_path():
    # path search init
    start_vertex_index = 0
    path_list[start_vertex_index] = 0
    path_heap = []
    # heapq: compare by tuple[0]
    hp.heappush(path_heap, (path_list[start_vertex_index], start_vertex_index))
    while len(path_heap) >= 1:
        current_vertex = hp.heappop(path_heap)[1]

        color[current_vertex] = BLACK

        for adj_vertex in range(vertices_num):
            current_adj_weight = adj_matrix[current_vertex].get(str(adj_vertex), -1)
            if current_adj_weight < 0:
                continue
            elif color[adj_vertex] is not BLACK:
                # d[u] + w[u,v]
                alt_path = path_list[current_vertex] + current_adj_weight
                if alt_path < path_list[adj_vertex]:
                    # update path_list
                    path_list[adj_vertex] = alt_path
                    # update heap
                    hp.heappush(path_heap, (alt_path, adj_vertex))
                    parent_list[adj_vertex] = current_vertex
                    color[adj_vertex] = GRAY

    return path_list


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices_num = int(_input[0])
    init_vertices_table = list(map(lambda x: x.split(), _input[1:]))
    # assert len(init_vertices_table) == vertices_num

    parent_list, path_list = [-1] * vertices_num, [D_MAX] * vertices_num
    color = [WHITE] * vertices_num
    init_adj_matrix = tuple(dict() for _ in range(vertices_num))
    adj_matrix = generate_adj_matrix(init_vertices_table)
    ans = dijkstra_path()
    for i, v in enumerate(ans):
        print(i, v)

Python: import sys, collections, heapq
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def dijkstra(G, s):
    que = []
    d = [INF]*len(G)
    d[s] = 0
    heapq.heappush(que, (d[s], s))

    while que:
        p = heapq.heappop(que)
        v = p[1]
        if d[v] < p[0]: continue
        for e in G[v]:
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heapq.heappush(que, (d[e[0]], e[0]))
    return d

def resolve():
    n = I()
    G = [[] for _ in range(n)]
    for i in range(n):
        ukvc = LI()
        u = ukvc[0]
        k = ukvc[1]
        for j in range(k):
            v = ukvc[2*j+2]
            c = ukvc[2*j+3]
            G[u].append((v, c))

    ans = dijkstra(G, 0)
    for i, e in enumerate(ans):
        print(i, e)

if __name__ == '__main__':
    resolve()

Python: from collections import namedtuple
import heapq

Edge = namedtuple('Edge', ('fr', 'to', 'cost'))
inf = int(1e9)


def bellman_ford(n, start, edges):
    dists = [inf for _ in range(n)]
    dists[start] = 0
    while True:
        updated = False
        for e in edges:
            if dists[e.fr] != inf and dists[e.fr] + e.cost < dists[e.to]:
                updated = True
                dists[e.to] = dists[e.fr] + e.cost

        if not updated:
            break

    return dists


def dijkstra(n, costs):
    dists = [inf for _ in range(n)]
    dists[0] = 0

    queue = []
    for (i, d) in enumerate(dists):
        heapq.heappush(queue, (d, i))

    while len(queue) > 0:
        d, i = heapq.heappop(queue)
        if d > dists[i]:
            continue

        for v in range(n):
            if v == i or costs[i][v] == inf:
                continue

            if dists[i] + costs[i][v] < dists[v]:
                dists[v] = dists[i] + costs[i][v]
                heapq.heappush(queue, (dists[v], v))

    return dists


def warshall_floyd(n, costs):
    for i in range(n):
        print(costs[i])

    dists = [[costs[i][j] for j in range(n)] for i in range(n)]

    for k in range(n):
        for i in range(n):
            for j in range(n):
                dists[i][j] = min(dists[i][j], dists[i][k] + dists[k][j])

    return dists


n = int(input())

m = [[inf if i != j else 0 for i in range(n)] for j in range(n)]
es = []
for i in range(n):
    fs = list(map(int, input().split()))
    ne = fs[1]
    for j in range(ne):
        v = fs[2+2*j]
        c = fs[2+2*j+1]
        m[i][v] = c
        es.append(Edge(i, v, c))


# d = bellman_ford(n, 0, es)
# d = dijkstra(n, m)
d = warshall_floyd(n, m)
for (i, di) in enumerate(d[0]):
    print(i, di)

Python: #coding: utf-8

inf = 1000000000


def dijkstra(s):
    d = [inf for i in range(n)]
    color = ["white" for i in range(n)]
    p = [-1 for i in range(n)]
    d[s] = 0

    while True:
        mincost = inf
        for i in range(n):
            if color[i] != "black" and d[i] < mincost:
                mincost = d[i]
                u = i
        if mincost == inf:
            break

        color[u] = "black"

        for v in range(n):
            if color[v] != "black" and mtrx[u][v] != False:
                if d[u] + mtrx[u][v] < d[v]:
                    d[v] = d[u] + mtrx[u][v]
                    p[v] = u
                    color[v] = "gray"
    return d

n = int(input())
mtrx = [[False for j in range(n)] for i in range(n)]
for i in range(n):
    data = list(map(int,input().split()))
    k = data[1]
    for num in range(k):
        mtrx[i][data[2+2*num]] = data[2+2*num+1]

d = dijkstra(0)

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

Python: # ALDS1_12_V Single Source Shortest Path I
import sys

n = int(input())
G = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    ukvc = list(map(int, sys.stdin.readline().strip().split()))
    u = ukvc[0]
    k = ukvc[1]

    for j in range(k):
        G[u][ukvc[2 + 2 * j]] = ukvc[3 + 2 * j]

p = [n] * n  # 親を保存するリスト　親ノードとしてあり得ない n を初期リストとする
c = ['white'] * n # 最小経路木への接続チェック　white 未接続　black 接続済
d = [float('inf')] * n  # ノード i までの最小経路を保存するリスト
d[0] = 0  # 根への距離は0とする
p[0] = -1  # 根の親は -1 とする
u = 0  # 次のループで最小経路木につなげるノード

while 'white' in c:
    c[u] = 'black'

    v = None
    minpath = float('inf')
    for i in range(n):
        d[i] = min(d[i], d[u] + G[u][i])
        if (d[i] < minpath) & (c[i] == 'white'):
            minpath = d[i]
            v = i
            p[i] = u

    if v is None:
        break

    u = v

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