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: 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(alt, 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)

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: #!/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 = 1 << 20


def generate_adj_matrix(v_info):
    for each in v_info:
        v_index, v_adj_length, *v_adj_list = map(int, each)
        # assert len(v_adj_list) == v_adj_length * 2
        for pair in zip(v_adj_list[::2], v_adj_list[1::2]):
            init_adj_matrix[v_index][pair[0]] = pair[1]

    return init_adj_matrix


def dijkstra_path():
    # path search init
    path_list[init_vertex_index] = 0
    path_heap = []
    # heapq: rank by tuple[0], here ranked by d[u]
    hp.heappush(path_heap, (0, init_vertex_index))
    while len(path_heap) >= 1:
        current_vertex_index = hp.heappop(path_heap)[1]

        color[current_vertex_index] = BLACK

        current_vertex_index_info = adj_table[current_vertex_index]
        for adj_vertex_index in current_vertex_index_info.keys():
            current_adj_weight = current_vertex_index_info.get(adj_vertex_index)
            if not current_adj_weight:
                continue
            elif color[adj_vertex_index] is not BLACK:
                # alt: d[u] + w[u,v]
                alt_path = path_list[current_vertex_index] + current_adj_weight
                if alt_path < path_list[adj_vertex_index]:
                    # update path_list
                    path_list[adj_vertex_index] = alt_path
                    # update heap
                    hp.heappush(path_heap, (alt_path, adj_vertex_index))
                    parent_list[adj_vertex_index] = current_vertex_index
                    color[adj_vertex_index] = GRAY

    return path_list


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices_num = int(_input[0])
    init_vertices_table = 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))
    init_vertex_index = 0

    adj_table = generate_adj_matrix(init_vertices_table)
    ans = dijkstra_path()
    for i, v in enumerate(ans):
        print(i, v)