Go: package main

import (
	"strconv"
	"fmt"
	"bufio"
	"os"
)
const INF = 1 << 21
var scanner = bufio.NewScanner(os.Stdin)

func nextInt() int {
	scanner.Scan()
	i, e := strconv.Atoi(scanner.Text())
	if e != nil {
		panic(e)
	}
	return i
}


func main() {
	scanner.Split(bufio.ScanWords)
	n := nextInt()
	adj := make([][]int, n)
	for i := range adj {
		adj[i] = make([]int, n)
	}

	for i := 0;i < n; i++ {
		u := nextInt()
		k := nextInt()
		for j := 0; j < k; j++ {
			v := nextInt()
			c := nextInt()
			adj[u][v] = c
		}
	}

	// for i := range adj {
	// 	fmt.Println(adj[i])
	// }

	dist := make([]int, n)
	prev := make([]int, n)
	visited := make([]bool, n)
	dijkstra := func(start int, size int) {
		for i := 0; i < size; i++ {
			dist[i] = INF
			prev[i] = -1
			visited[i] = false
		}
		dist[start] = 0
		for {
			u := -1
			tmp_min := INF
			for i := 0; i < size; i++ {
				if visited[i] == false && dist[i] < tmp_min {
					tmp_min = dist[i]
					u = i
				}
			}
			if u == -1 {
				break
			}
			visited[u] = true
			for i := 0; i < size; i++ {
				if adj[u][i] > 0 {
					w := adj[u][i]
					newlen := dist[u] + w
					if newlen < dist[i] {
						dist[i] = newlen
						prev[i] = u
					}
				}
			}
		}
	}
	dijkstra(0, n)
	for i, cost := range dist {
		fmt.Printf("%d %d\n", i, cost)
	}
}

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