Go: package main

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

//make priority queue
type Item struct {
	id       int
	priority int // this state is priority and distans from start
	index    int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

// we want the ascending-priority-queue.
// So we use less than here.
func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority < pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = j
	pq[j].index = i
}

func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	item.index = -1 //for safety
	*pq = old[0 : n-1]
	return item
}

func (pq *PriorityQueue) update(dist int, id int) {
	for _, i := range *pq {
		if i.id == id {
			if i.priority > dist {
				i.priority = dist
			}
		}
	}
}

// the main code
func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())
	return n
}

func dikstra(dist *[][]int, n int) *[]int {
	// preparate priority queue
	inf := 1 << 30
	pq := make(PriorityQueue, n)
	shortests := make([]int, n)
	for i := 0; i < n; i++ {
		pq[i] = &Item{
			id:       i,
			priority: inf,
			index:    i,
		}

		shortests[i] = inf
	}
	pq[0].priority = 0
	shortests[0] = 0
	heap.Init(&pq)

	for pq.Len() > 0 {
		item := heap.Pop(&pq).(*Item)
		shortests[item.id] = item.priority
		for id, d := range (*dist)[item.id] {
			if d != -1 {
				pq.update(item.priority+d, id)
			}
		}
		heap.Init(&pq)
	}
	return &shortests
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	// init
	n := nextInt(sc)
	dist := make([][]int, n)
	for i := 0; i < n; i++ {
		dist[i] = make([]int, n)
		for j := 0; j < n; j++ {
			dist[i][j] = -1
		}
	}

	// std Input
	for i := 0; i < n; i++ {
		u := nextInt(sc)
		k := nextInt(sc)
		for j := 0; j < k; j++ {
			v, c := nextInt(sc), nextInt(sc)
			dist[u][v] = c
		}
	}

	shortests := dikstra(&dist, n)
	for i, d := range *shortests {
		fmt.Printf("%d %d\n", i, d)
	}
}

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])