Go: package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
)

type Item struct {
	value    int // The value of the item; arbitrary.
	priority int // The priority of the item in the queue.
	// The index is needed by update and is maintained by the heap.Interface methods.
	index int // The index of the item in the heap.
}
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority < pq[j].priority
}
func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}
func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	item.index = -1 // for safety
	*pq = old[0 : n-1]
	return item
}

type Q struct {
	pq *PriorityQueue
	ds map[int]int // It has always same value as pq. For random access.
}

func newQ() *Q {
	pq := new(PriorityQueue)
	heap.Init(pq)
	return &Q{
		pq: pq,
		ds: make(map[int]int),
	}
}
func (q *Q) pop() (u, d int) {
	item := heap.Pop(q.pq).(*Item)
	delete(q.ds, item.value)
	return item.value, item.priority
}
func (q *Q) get(u int) (int, bool) { // returns d
	d, ok := q.ds[u]
	return d, ok
}
func (q *Q) set(u, d int) {
	q.ds[u] = d
	for _, item := range *q.pq {
		if item.value != u {
			continue
		}

		item.priority = d
		heap.Fix(q.pq, item.index)
		return
	}
	heap.Push(q.pq, &Item{
		priority: d,
		value:    u,
	})
}
func (q *Q) len() int {
	return len(q.ds)
}

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 := newQ()
	q.set(0, 0)
	visited := make(map[int]struct{})
	out := make([]int, n)

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

		out[u] = d
		visited[u] = struct{}{}
	}

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

Python: import sys
from math import 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: # -*- coding: utf-8 -*-
from heapq import heappush, heappop

N = int(input())
INF = float("inf")
adj = []
for _ in range(N):
    inp = tuple(map(int, input().split()))
    adj.append(tuple(zip(inp[2::2], inp[3::2])))

checked = [False for _ in range(N)]
d = [float("inf") for _ in range(N)]
d[0] = 0

heap = [[0, 0]] # cost, vec

while heap:
    c, u = heappop(heap)
    if d[u] < c or checked[u]:
        continue
    for nu, nc in adj[u]:
        new_d = d[u] + nc
        if new_d < d[nu]:
            d[nu] = new_d
            heappush(heap, [d[nu], nu])
    checked[u] = True

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

Python: n = int(input())
ukvc = [ list(map(int,input().split())) for _ in range(n) ]

g = [ [] for _ in range(n) ]
for i in range(n):
    ls = ukvc[i]
    u = ls[0]
    k = ls[1]
    vc = ls[2:]
    for j in range(k):
        v = vc[2*j]
        c = vc[2*j+1]
        g[u].append([c,v])
# print(g)


# Dijkstra法(O(ElogV))
# edge[i] : iから出る道の[重み,行先]の配列
import heapq
def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n # True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

d = dijkstra_heap(0,g)

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

Python: import heapq


class Graph(object):

    class Node:
        def __init__(self, dist: int, number: int):
            self.dist = dist
            self.number = number

        def __lt__(self, other):
            return self.dist < other.dist \
                   or (self.dist == other.dist
                       and self.number < other.number)

        def __le__(self, other):
            return self.dist <= other.dist

        def __gt__(self, other):
            return other <= self

        def __ge__(self, other):
            return other < self

        def __str__(self):
            return "Node: (" + str(self.number) + ", " \
                   + str(self.dist) + ")"

    class Edge:
        def __init__(self, to: int, cost: int):
            self.to = to
            self.cost = cost

        def __str__(self):
            return "Edge: (" + str(self.to) + ", " \
                   + str(self.cost) + ")"

    INF = 10e10

    def __init__(self, node_n: int, start: int):
        self.node_n = node_n
        self.start = start
        self.edges = [{} for _ in range(self.node_n)]
        self.dist = [self.INF for _ in range(self.node_n)]

    def set_edge(self, from_pos: int, to_pos: int, cost: int, reversible: bool) -> None:
        self.edges[from_pos][to_pos] = (self.Edge(to_pos, cost))
        if reversible:
            self.edges[to_pos][from_pos] = (self.Edge(from_pos, cost))

    def solve(self) -> list:
        raise NotImplementedError


class Dijkstra(Graph):
    hq = []
    prev: list

    def __init__(self, node_n: int, start: int):
        super(Dijkstra, self).__init__(node_n, start)
        self.dist[self.start] = 0
        self.prev = [None for _ in range(node_n)]

    def solve(self) -> list:
        heapq.heappush(self.hq, self.Node(0, self.start))

        while len(self.hq) != 0:
            node = heapq.heappop(self.hq)
            if node.dist > self.dist[node.number]:
                continue

            for edge in self.edges[node.number].values():
                alt = self.dist[node.number] + edge.cost
                if self.dist[edge.to] > alt:
                    self.dist[edge.to] = alt
                    self.prev[edge.to] = node.number
                    heapq.heappush(self.hq, self.Node(self.dist[edge.to], edge.to))

        return self.dist


if __name__ == '__main__':
    n = int(input())
    graph = Dijkstra(n, 0)

    for _ in range(n):
        buff = list(map(int, input().split()))
        u = buff[0]
        k = buff[1]
        for i in range(k):
            graph.set_edge(u,
                           buff[2 + i * 2],
                           buff[3 + i * 2],
                           False)
    dist = graph.solve()
    for i, d in enumerate(dist):
        print(i, d)