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: def E_dijkstra(V,AL,S):
    from heapq import heappush,heappop
    INF=float('inf')
    ans=[INF]*V
    ans[S]=0
    used=[0]*V # 0:未確定
    used[S]=1
    que=[]
    for i in range(V):
        heappush(que,(ans[i],i))
    while que:
        x,u=heappop(que)
        used[u]=1
        for v,w in AL[u]:
            if not used[v] and ans[v]>x+w:
                ans[v]=x+w
                heappush(que,(ans[v],v))
    return ans

# verified: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_A
# import sys
# input = sys.stdin.readline
# V,E,R=map(int,input().split())
# AL=[[] for i in range(V)]
# for _ in range(E):
#     S,T,D=map(int,input().split())
#     AL[S].append((T,D))
# for ans in E_dijkstra(V,AL,R):
#     print('INF' if ans==float('inf') else ans)

import sys
input = sys.stdin.readline

N=int(input())
AL=[[] for _ in range(N)]
for _ in range(N):
    for i,x in enumerate(input().split()):
        x=int(x)
        if i==0:
            j=x
        elif i==1:
            pass
        else:
            if i%2==0:
                tmp=[x]
            else:
                tmp.append(x)
                AL[j].append(tmp)
for ans in enumerate(E_dijkstra(N,AL,0)):
    print(*ans)

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 = int(5e10 + 1)


def generate_adj_matrix():
    for each in init_vertices_table:
        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 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()
    ans = dijkstra_path()
    for i, v in enumerate(ans):
        print(i, v)

Python: import heapq

n = int(input())
C = [[] for _ in range(n)]
for _ in range(n):
    tmp = list(map(int,input().split()))
    for i in range(1,tmp[1]+1):
        C[tmp[0]].append(tuple(tmp[2*i:2*i+2]))

q = []

def heap_dijkstra(start = 0):
    visited = [False]*n
    INF = 10000000000
    d = [INF]*n

    d[start] = 0
    visited[start] = True
    add_node = start

    for i in range(n-1):
        for adj_weight in C[add_node]:
            if visited[adj_weight[0]] == False:
                heapq.heappush(q,(d[add_node]+adj_weight[1],adj_weight[0]))

        while 1:
            tmp = heapq.heappop(q)
            if visited[tmp[1]] == False:
                min_weight = tmp[0]
                min_node = tmp[1]
                break
        
        add_node = min_node
        visited[min_node] = True
        d[min_node] = min_weight
    
    return d

D = heap_dijkstra()

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

Python: n = int(input())
adjacents = []
inf =  999999999999999
distances = [inf] * n
colors  = ["white"] * n
from heapq import heappush, heappop

for i in range(n):
  u, k, *a = map(int, input().split())
  adjacents.append([])
  for l in range(k):
    v = a[(l * 2)]
    c = a[(l * 2 + 1)]
    adjacents[u].append([v, c])

def dijkstra(u):
  distances[u] = 0
  queue = []
  heappush(queue, [0, u])

  while queue:
    w, u = heappop(queue)
    
    if distances[u] < w:
      continue
    
    colors[u] = "black"
    distances[u] = w

    for edge, weight in adjacents[u]:
      if colors[edge] != "black" and distances[edge] > weight + w:
        heappush(queue, [weight + w, edge])

dijkstra(0)

for index, edge in enumerate(distances):
  print(index, edge)