Go: package main

import (
	"fmt"
	"os"
	"bufio"
	"strings"
	"strconv"
)
var MAX = 1000000
type Vertex struct{
	Value int
	Routes map[int]int
	Done bool
}
func NewVertex(value int) *Vertex{
	routes := make(map[int]int)
	// for i, _ := range routes {
	// 	routes[i] = MAX
	// }
	return &Vertex{ value, routes, false }
}

func (v *Vertex) SetRoute(key, weight int) {
	v.Routes[key] = weight
}

type Path struct {
	Key int
	Weight int
}

var count = 0
func ShortestRoutes(list []*Vertex) []int {
	// create result table
	result  := make([]int, len(list))
	// fmt.Println(result)
	for i, _ := range result {
		result[i] = MAX
	}

	queue := make([]Path, 0)
	queue = append(queue, Path{0, 0})
	result[0] = 0

	for len(queue) != 0 {
		count++
		path := queue[0]
		queue = queue[1:]
		for key, weight := range list[path.Key].Routes {
			// fmt.Println(list[path.Key].Routes)
			// set to result
			// fmt.Printf("Path(%d, %d) ? result[%d] => %d, wieght: %d\n", path.Key, path.Weight, key, result[key], weight)
			if path.Weight + weight < result[key] {
				result[key] = path.Weight + weight 
				queue = append(queue, Path{key, result[key]})
			// } else if !list[key].Done {
			// 	queue = append(queue, Path{key, result[key]})
			}
		}
		list[path.Key].Done = true
	}
	return result
}
func main() {
	var n int
	fmt.Scanf("%d", &n)
	list := make([]*Vertex, n)
	scanner := bufio.NewScanner(os.Stdin)
	for i := 0; i < n; i++ {
		scanner.Scan()
		elements := strings.Split(scanner.Text(), " ")
		value, _ := strconv.Atoi(elements[0])
		list[i] = NewVertex(value)
		for j := 2; j < len(elements); j += 2 {
			key, _    := strconv.Atoi(elements[j])
			weight, _ := strconv.Atoi(elements[j + 1])
			list[i].SetRoute(key, weight)
		}
	}

	result := ShortestRoutes(list)
	for i := 0; i < len(result); i++ {
		fmt.Printf("%d %d\n", i, result[i]);
	}
	// fmt.Printf("count: %d\n", count)
}

Python: import sys,collections
N = int(sys.stdin.readline())
G = tuple(tuple(map(int,sys.stdin.readline().rstrip().split()))[2:] for _ in range(N)) # multi line with multi param
# n x n adjacency matrix
#G = [[-1,2,3],[2,-1,3],[1,2,-1]]
INF = float("inf")
ALL = set(range(N))
mst = set()
distances = [INF]*N # 蟋狗せ0縺九ｉ縺ｮ霍晞屬
distances[0] = 0
parents = [INF]*N
parents[0] = 0

import heapq

dv = []
def add(u):
  mst.add(u)
  if not ALL-mst: return
  for j in range(0,len(G[u]),2):
    v = G[u][j]
    w = G[u][j+1]
    if not v in mst and w + distances[u] < distances[v]: # u繧堤ｵ檎罰縺励◆譁ｹ縺悟ｮ峨＞
      distances[v] = distances[u]+w
      parents[v] = u
      heapq.heappush(dv, (distances[v],v))
  #print(distances)
  d,v = heapq.heappop(dv)
  while v in mst:
    d,v = heapq.heappop(dv)
  return v

n = add(0)
distances[0] = 0
parents[0]=0
while len(mst) < len(G):
  n = add(n)

for i in range(N):
  print(i,distances[i])

Python: from heapq import*
def m():
 n=int(input())
 A=[]
 for _ in[0]*n:
  e=list(map(int,input().split()))
  A+=[zip(e[2::2],e[3::2])]
 d=[0]+[float("inf")]*n
 H=[(0,0)]
 while H:
  u=heappop(H)[1]
  for v,c in A[u]:
   t=d[u]+c
   if d[v]>t:
    d[v]=t
    heappush(H,(t,v))
 print('\n'.join(f'{i} {d[i]}'for i in range(n)))
m()

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():
    # path search init
    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:
                # d[u] + w[u,v]
                alt_path = path_list[current_vertex] + current_adj_weight
                if alt_path < path_list[adj_vertex]:
                    # update path_list
                    path_list[adj_vertex] = alt_path
                    # update heap
                    hp.heappush(path_heap, (alt_path, 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 heapify, heappop, heappush, heappushpop
INF = 10**6 + 1

class PriorityQueue:
    def __init__(self, heap):
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

    def __len__(self):
        return len(self.heap)


def dijkstra(adj: list, s: int):
    Color = [0] * N
    D = [INF] * N
    P = [None] * N

    D[s] = 0
    P[s] = None
    PQ = PriorityQueue([(0, s)])

    while PQ:
        min_cost, u = PQ.pop()

        Color[u] = 2

        if D[u] < min_cost:
            continue

        for idx_adj_u, w_adj_u in adj[u]:
            if Color[idx_adj_u] != 2:
                if D[u] + w_adj_u < D[idx_adj_u]:
                    D[idx_adj_u] = D[u] + w_adj_u
                    P[idx_adj_u] = u
                    PQ.push((D[idx_adj_u], idx_adj_u))
                    Color[idx_adj_u] = 1
    return D, P

N = int(input())
adj = [[] for _ in range(N)]
for _ in range(N):
    tmp = list(map(int, input().split()))
    if tmp[1] != 0:
        node = tmp[0]
        for i in range(2, 2 + tmp[1] * 2, 2):
            adj[node].append((tmp[i], tmp[i + 1]))

D, P = dijkstra(adj, 0)

for i in range(N):
    print(i, D[i])

Python: V=int(input())
 
G=[[] for i in range(V)]
d=[1001001001 for i in range(V)]
used=[False for i in range(V)]
 
import heapq
 
def dijkstra(s):
    q=[]
    d[s]=0
    heapq.heappush(q,(0, s))
     
    while(len(q)):
         
        p=heapq.heappop(q)
        v=p[1]
        used[v]=true
        if d[v]<p[0]:
            continue
        for e in G[v]:
            if (not used[e[0]]) and d[e[0]]>d[v]+e[1]:
                d[e[0]]=d[v]+e[1]
                 
                heapq.heappush(q, (d[e[0]], e[0]))
 
import sys
for l in sys.stdin:
    l=list(map(int,l.split()))
    u=l[0]
    k=l[1]
    G[u]=zip(*[iter(l[2:])]*2)
     
dijkstra(0)
for i, c in enumerate(d):
    print(i, d[i])