Go: package main

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

const NIL = -1

type Node struct {
	id     int
	weight int
}

func init() {
	sc.Split(bufio.ScanWords)
}

type NodeHeap []Node

func (h NodeHeap) Len() int           { return len(h) }
func (h NodeHeap) Less(i, j int) bool { return h[i].weight < h[j].weight }
func (h NodeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *NodeHeap) Push(x interface{}) {
	*h = append(*h, x.(Node))
}

func (h *NodeHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	num, _ := strconv.Atoi(scanString())
	return num
}

func scanString() string {
	sc.Scan()
	return sc.Text()
}

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	n := scanInt()

	route := make([][]Node, n)
	weight := make([]int, n)
	for i := 0; i < n; i++ {
		weight[i] = NIL
	}

	for i := 0; i < n; i++ {
		u := scanInt()
		k := scanInt()
		route[i] = make([]Node, k)
		for j := 0; j < k; j++ {
			route[u][j] = Node{id: scanInt(), weight: scanInt()}
		}
	}

	start := Node{id: 0, weight: 0}
	h := &NodeHeap{start}
	heap.Init(h)

	for h.Len() > 0 {
		node := heap.Pop(h).(Node)
		if weight[node.id] != NIL {
			continue
		}
		weight[node.id] = node.weight

		for _, nextNode := range route[node.id] {
			if weight[nextNode.id] != NIL {
				continue
			}
			nextNode.weight += node.weight
			heap.Push(h, nextNode)
		}
	}

	for i, w := range weight {
		fmt.Println(i, w)
	}
}

Python: from sys import maxsize
from heapq import heappop, heappush


class Node:
    WHITE = 0
    GRAY = 1
    BLACK = 2

    def __init__(self):
        self.adjs = []
        self.color = Node.WHITE
        self.dist = maxsize

    def __lt__(self, other):
        return self.dist < other.dist

    def __repr__(self):
        return "Node({},{},{})".format(self.adjs, self.color, self.dist)


def read_adj():
    n = int(input())
    nodes = [Node() for _ in range(n)]

    for i in range(n):
        u, _, *rest = [int(x) for x in input().split()]
        for i in range(0, len(rest) - 1, 2):
            nodes[u].adjs.append((rest[i], rest[i+1]))

    return nodes


def shortest_path(nodes):
    h = []

    nodes[0].dist = 0
    nodes[0].color = Node.GRAY
    heappush(h, (0, 0))

    while len(h) > 0:
        min_dist, min_node = heappop(h)

        nodes[min_node].color = Node.BLACK
        if nodes[min_node].dist < min_dist:
            continue

        for adj, c in nodes[min_node].adjs:
            if nodes[adj].color == Node.BLACK:
                continue
            if nodes[min_node].dist + c < nodes[adj].dist:
                nodes[adj].dist = nodes[min_node].dist + c
                nodes[adj].color = Node.GRAY
                heappush(h, (nodes[adj].dist, adj))


def print_dist(nodes):
    for u, n in enumerate(nodes):
        print(u, n.dist)


def main():
    nodes = read_adj()
    shortest_path(nodes)
    print_dist(nodes)


if __name__ == '__main__':
    main()

Python: import sys, itertools
f = sys.stdin

def take2(iterable):
    i = iter(iterable)
    while True:
        yield next(i), next(i)

n = int(f.readline())
adj =[[(v, c) for v, c in take2(map(int, f.readline().split()[2:]))] for _ in range(n)]
d = [100000 * 100 + 1] * n

d[0] = 0
queue ={0}
while len(queue):
    parent = queue.pop()
    for v, c in adj[parent]:
        if d[v] > d[parent] + c:
            d[v] = d[parent] + c
            queue.union([v])

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

Python: n = int(input())
G = [[-1 for i in range(n)] for j in range(n)]
d = [999999 for i in range(n)]
  
for i in range(n):
    v = input().split()
    for j in range(int(v[1])):
        G[int(v[0])][int(v[2+2*j])] = int(v[3+2*j])

flag = [0] * n
tn = [0]
d[0] = 0
for k in range(n):
    for i in range(n):
        if i in tn:
            for j in range(n):
                if G[i][j] != -1:
                    if d[j] > d[i] + G[i][j]:
                        d[j] = d[i] + G[i][j]
                    if j not in tn:
                        tn.append(j)
  
for i in range(n):
    print(str(i) + " " + str(d[i]))

Python: #coding:utf-8
n = int(input())
inf = 1000000000000000

def minHeapify(Q,i):
    H = len(Q)
    l = 2*i
    r = 2*i + 1
    if l < H and Q[l][1] < Q[i][1]:
        smallest = l
    else:
        smallest = i
    if r < H and Q[r][1] < Q[smallest][1]:
        smallest = r

    if smallest != i:
        Q[i], Q[smallest] = Q[smallest], Q[i]
        minHeapify(Q,smallest)

def buildMinHeap(Q):
    H = len(Q)
    for i in range(H // 2, -1, -1):
        minHeapify(Q,i)

def Insert(Q,key):
    v = key[0]
    Q.append([v,inf])
    lens = len(Q)
    heapIncreaseKey(Q,lens-1,key)

def heapIncreaseKey(Q,i,key):
    Q[i][1] = key[1]
    while i > 0 and Q[i // 2][1] > Q[i][1]:
        Q[i], Q[i // 2] = Q[i // 2], Q[i]
        i //= 2

def heapExtractMin(Q):
    H = len(Q)
    minv = Q[0][0]
    Q[0] = Q[H-1]
    Q.pop()
    minHeapify(Q,0)
    return minv




def dijkstra(s):
    color = ["white" for i in range(n)]
    d = [inf for i in range(n)]
    d[s] = 0
    Q = [[s,0]]
    while Q != []:
        u = heapExtractMin(Q)
        color[u] = "black"
        for vw in mtrx[u]:
            [v,w] = vw
            if color[v] != "black":
                if d[u] + w < d[v]:
                    d[v] = d[u] + w
                    color[v] = "gray"
                    Insert(Q,[v,d[v]])
    return d



mtrx = [[] for i in range(n)]
for i in range(n):
    col = list(map(int,input().split()))
    u,k = col[0], col[1]
    for j in range(k):
        [v,w] = col[2*j+2: 2*j+4]
        mtrx[u].append([v,w])



d = dijkstra(0)
for i,j in enumerate(d):
    print(i,j)

Python: if __name__ == '__main__':
    from sys import stdin
    input = stdin.readline

    import heapq
    from copy import deepcopy

    INFTY = 2**21
    WHITE = 0
    GRAY = 1
    BLACK = 2

    n = int(input())

    adj = [0]*n

    for _ in range(n):
        u, k, *vc = map(int, input().split())
        vc_tuple = [0]*k
        for i, (v, c) in enumerate(zip(vc[::2], vc[1::2])):
            # pythonにはvectorないので、tupleで代用
            vc_tuple[i] = (v, c)
        adj[u] = vc_tuple

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

        d[0] = 0
        PQ = [(0, 0)]
        heapq.heapify(PQ) # PQを優先度付きキューにする
        color[0] = GRAY
        while PQ:  # PQの長さ0でwhile抜ける
            f = heapq.heappop(PQ)
            u = f[1]
            color[u] = BLACK

            # 最小値を取り出し、それが最短でなければ無視
            if d[u] < f[0]: # -1かけない理由は9行下のコメント参照
                continue

            for adj_u in adj[u]:
                v = adj_u[0]
                if color[v] == BLACK:
                    continue
                if d[v] > d[u]+adj_u[1]:
                    d[v] = d[u]+adj_u[1]
                    # pythonのheapqはmin-ヒープを使っているので-1かけなくて良い
                    heapq.heappush(PQ, (d[v], v))
                    color[v] = GRAY

        for i in range(n):
            print(str(i) + ' ' + str(-1 if d[i] == INFTY else d[i]))

    dijkstra()

    """

    nodes = [[] for _ in range(n)]

    for _ in range(n):
        u, k, *vc = map(int, input().split())
        cv = [0]*k
        for i, (v, c) in enumerate(zip(vc[::2], vc[1::2])):
            cv[i] = (c, v)
        nodes[u] = cv

    d = [INFTY]*n
    d[0] = 0

    d_node = nodes[0]
    heapq.heapify(d_node)

    visited = [False]*n
    visited[0] = True

    while d_node:
        min_c, min_v = heapq.heappop(d_node)
        if visited[min_v]:
            continue
        visited[min_v] = True
        d[min_v] = min_c
        for c, v in nodes[min_v]:
            heapq.heappush(d_node, (min_c+c, v))

    for u, dist in enumerate(d):
        print(str(u) + ' ' + str(dist))
    """