Go: package main

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

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func ceil(a, b int) int {
	if a%b == 0 {
		return a / b
	} else {
		return a/b + 1
	}
}

// Sort
type RuneSlice []rune

func (a RuneSlice) Len() int           { return len(a) }
func (a RuneSlice) Less(i, j int) bool { return a[i] < a[j] }
func (a RuneSlice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

// Main
const INF = 1 << 60

type Edge struct {
	to, cost int
}

type Node struct {
	id, cost int
}

type PQ []Node

func (pq PQ) Len() int           { return len(pq) }
func (pq PQ) Less(i, j int) bool { return pq[i].cost < pq[j].cost }
func (pq PQ) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }

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

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

func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	N := sc.nextInt()
	E := make([][]Edge, N)
	for i := 0; i < N; i++ {
		id, k := sc.nextInt(), sc.nextInt()
		E[id] = make([]Edge, k)
		for j := 0; j < k; j++ {
			to, cost := sc.nextInt(), sc.nextInt()
			E[id][j] = Edge{to, cost}
		}
	}

	d := make([]int, N)
	for i := 0; i < N; i++ {
		d[i] = INF
	}
	done := make([]bool, N)
	pq := &PQ{}
	heap.Init(pq)
	d[0] = 0
	heap.Push(pq, Node{0, 0})
	for pq.Len() > 0 {
		cur := heap.Pop(pq).(Node).id
		if done[cur] {
			continue
		}
		done[cur] = true
		for i := 0; i < len(E[cur]); i++ {
			to, cost := E[cur][i].to, E[cur][i].cost+d[cur]
			if !done[to] && cost < d[to] {
				d[to] = cost
				heap.Push(pq, Node{to, cost})
			}
		}
	}

	for i := 0; i < N; i++ {
		fmt.Fprintln(wtr, i, d[i])
	}
	wtr.Flush()
}

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(1e7 + 1)


def generate_adj_matrix(v_info):
    for v_detail in v_info:
        v_index = int(v_detail[0])
        v_adj_length = int(v_detail[1])
        v_adj_list = v_detail[2:]
        # assert len(v_adj_list) == v_adj_length * 2
        for j in range(0, v_adj_length * 2, 2):
            init_adj_matrix[v_index][v_adj_list[j]] = int(v_adj_list[j + 1])

    return init_adj_matrix


def dijkstra_path():
    start_vertex_index = 0
    path_list[start_vertex_index] = 0
    path_heap = []
    # heapq: compare by tuple[0]
    hp.heappush(path_heap, (path_list[start_vertex_index], start_vertex_index))
    while len(path_heap) >= 1:
        current_vertex = hp.heappop(path_heap)[1]

        color[current_vertex] = BLACK

        for adj_vertex in range(vertices_num):
            current_adj_weight = adj_matrix[current_vertex].get(str(adj_vertex), -1)
            if current_adj_weight < 0:
                continue
            elif color[adj_vertex] is not BLACK:
                if path_list[current_vertex] + current_adj_weight < path_list[adj_vertex]:
                    # update path_list
                    path_list[adj_vertex] = path_list[current_vertex] + current_adj_weight
                    # update heap
                    hp.heappush(path_heap, (path_list[adj_vertex], adj_vertex))
                    parent_list[adj_vertex] = current_vertex
                    color[adj_vertex] = GRAY

    return path_list


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices_num = int(_input[0])
    init_vertices_table = list(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))
    adj_matrix = generate_adj_matrix(init_vertices_table)
    ans = dijkstra_path()
    for j in range(vertices_num):
        print(j, ans[j])

Python: from heapq import *
n = int(input())
INF = float("inf")
adj = [[] for _ in range(10**4+4)]
for _ in range(n):
    a,*b = map(int,input().split())
    if b[0] != 0:
        c = b[1:]
        for i in range(len(c)//2):
            k,w = c[2*i],c[2*i+1]
            adj[a].append((k,w))
H = []
heapify(H)
searched = [0]*n
d = [INF]*n
d[0] = 0
heappush(H, (0,0))
while H:
    f = heappop(H)
    u = f[-1]
    searched[u] = 1
    if d[u] < f[0]:
        continue
    for j in range(len(adj[u])):
        v = adj[u][j][0]
        if searched[v]:
            continue
        if d[v] > d[u]+adj[u][j][-1]:
            d[v] = d[u]+adj[u][j][-1]
            heappush(H,(d[v],v))
for i in range(n):
    ans = -1 if d[i] == INF else d[i]
    print(i,ans)

Python: from collections import deque

n = int(input())
g = []
d = [10**10] * n
d[0] = 0

for i in range(n):
    temp = list(map(int, input().split()))
    k = temp[1]
    temp = temp[2:]
    adj = []
    for j in range(k):
        v, c = temp[j*2], temp[j*2+1]
        adj.append([v, c])
    g.append(adj)

# for i in range(n):
#     print(g[i])

q = deque()
# Add tupple of prev and adj into Queue
q.append((0, g[0]))
done = set()

while q:
    node = q.popleft()
    prev = node[0]
    adj = node[1]
    # print('\nadj:', adj)

    for next in adj:
        v = next[0]
        w = next[1]
        # print('v:', v)
        # print('prev:', prev)

        # d[v] = min(d[v], d[prev] + w)
        if d[prev] + w < d[v]:
            d[v] = d[prev] + w
            # Need to add to Queue regardless of it's in done or not,
            # because the shortest path was updated.
            q.append((v, g[v]))
        if v not in done:
            done.add(v)
            q.append((v, g[v]))

# print('d:', d)

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

Python: from heapq import*
n=int(input())
A=[[]for _ in[0]*n]
for _ in[0]*n:
 e=list(map(int,input().split()))
 for i in range(e[1]):k=2*-~i;A[e[0]]+=[(e[k],e[k+1])]
H=[[0,0]]
d=[0]+[1e6]*n
c=[1]*n
while H:
 f=heappop(H)
 u=f[1]
 c[u]=0
 if d[u]>=f[0]:
  for s in A[u]:
   v=s[0]
   if c[v]and d[v]>d[u]+s[1]:
    d[v]=d[u]+s[1]
    heappush(H,[d[v],v])
for i in range(n):print(i,d[i])