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

	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: from heapq import*
I=float("inf")
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]+[I]*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: 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)