Go: package main

import (
	"fmt"
	"container/heap"
)

type Node struct {
	Id int
	Dis int
}

type PriorityQueue []*Node

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].Dis < pq[j].Dis
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(*Node))
}

func (pq *PriorityQueue) Pop() interface{} {
	n := len(*pq)
	pop := (*pq)[n-1]
	*pq = (*pq)[0:n-1]
	return pop
}

func main() {
	var n int
	fmt.Scan(&n)

	g := make([][]int, n)
	c := make([][]int, n)
	pq := make(PriorityQueue, 0, n)
	d := make([]int, n)
	for i := 0; i < n; i++ {
		var u,k int
		fmt.Scan(&u)
		fmt.Scan(&k)
		g[u] = make([]int, k)
		c[u] = make([]int, k)
		for j := 0; j < k; j++ {
			fmt.Scan(&g[u][j])
			fmt.Scan(&c[u][j])
		}

		if u == 0 {
			d[u] = 0
		} else {
			d[u] = 1 << 30
		}
		pq.Push(&Node{u, d[u]})
	}
	heap.Init(&pq)

	for pq.Len() > 0 {
		node := heap.Pop(&pq).(*Node)
		for i := 0; i < len(g[node.Id]); i++ {
			nextId := g[node.Id][i]
			nextDis := node.Dis + c[node.Id][i]
			if nextDis < d[nextId] {
				d[nextId] = nextDis
				heap.Push(&pq, &Node{nextId, nextDis})
			}
		}
	}

	for i := 0; i < n; i++ {
		fmt.Println(i, d[i])
	}
}

Python: n = int(input())
adj = [[float('inf')]*n for _ in range(n)]
for i in range(n):
    a = list(map(int, input().split()))
    for j,k in zip(a[2::2], a[3::2]):
        adj[i][j] = k
color = [0]*n
d = [float('inf')]*n
d[0] = 0

while 1:
    mincost = float('inf')
    for i in range(n):
        if color[i] != 1 and d[i] < mincost:
            mincost = d[i]
            u = i
    if mincost == float('inf'):
        break
        
    color[u] = 1
    
    for i in range(n):
        if color[i] != 1 and adj[u][i] != float('inf'):
            if d[u]+adj[u][i] < d[i]:
                d[i] = d[u] + adj[u][i]
                
for i in range(n):
    print(i, d[i])

Python: def dijkstra(s):
    color = ["white" for i in range(n)]

    d = [inf 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 ci[u][v] != inf:
                if d[u] + ci[u][v] < d[v]:
                    d[v] = d[u] + ci[u][v]
                    p[v] = u
                    color[v] = "gray"
    return d


inf = 10 ** 9
n = int(input())
ci = [[inf for i in range(n)] for j in range(n)]

for i in range(n):
    data = list(map(int, input().split()))
    u = data[0]
    k = data[1]

    for j in range(0, 2*k, 2):
        v, w = data[j+2], data[j+3]
        ci[u][v] = w

dList = dijkstra(0)

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

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):
    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: rootList = [-1 for i in range(n)]
parent = [0 for i in range(n)]
lenList = [0 for i in range(n)]

def getRoot(x):
    r = rootList[x]
    if r < 0:
        rootList[x] = x
    elif r != x:
        rootList[x] = getRoot(r)
    return rootList[x]


edgeList.sort(key=lambda x: x[0])
flag = True
while flag:
    flag = False
    for e in edgeList:    # weight:e[0], e[1]->e[2]
        if e[2] == 0:
            continue
        x = getRoot(e[1])
        y = getRoot(e[2])
        if x == 0 != y:
            parent[e[2]] = e[1]
            lenList[e[2]] += lenList[e[1]] + e[0]
            rootList[y] = 0
            flag = True
            break

for i, j in zip(range(n), lenList):
    print(i, j)

Python: n = int(input())
from collections import defaultdict
G = defaultdict(list)
for i in range(n):
    i = [int(i) for i in input().split()]
    k = i[1]
    G[i[0]] = list(zip(i[2::2],i[3::2]))

def mind(Q, d):
    c = float('inf')
    ret = 0
    for i, j in enumerate(d):
        if c > j and i in Q:
            c = j
            ret = i
    return ret

def dijkstra(G):
    d = [0] + [float('inf')] * (n - 1)
    Q = set(range(n))
    while len(Q) != 0:
        u = mind(Q, d)
        Q = Q - set([u])
        for v, c in G[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
    return d

for i,j in enumerate(dijkstra(G)):
    print(i, j)

Python: from collections import namedtuple

Edge = namedtuple('Edge', ('fr', 'to', 'cost'))
inf = 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
    determined = [False for _ in range(n)]

    while True:
        v, min_d = -1, inf
        for i in range(n):
            if determined[i]:
                continue
            if dists[i] < min_d:
                v, min_d = i, dists[i]

        if v == -1:
            break

        determined[v] = True

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

            dists[i] = min(dists[i], dists[v] + costs[v][i])

    return dists


n = int(input())

m = [[-1 for _ in range(n)] for _ 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)
for (i, di) in enumerate(d):
    print(i, di)