Go: package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const BIG_COST = 200000

type Path struct {
	node int
	cost int
}

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

	nNodes := scanInt(sc)

	// 各頂点につながる頂点一覧を得るための隣接リスト
	graph := make([][]Path, nNodes)

	for i := 0; i < nNodes; i++ {
		u := scanInt(sc)
		k := scanInt(sc)
		graph[i] = make([]Path, k)
		for d := 0; d < k; d++ {
			graph[u][d] = Path{
				node: scanInt(sc),
				cost: scanInt(sc),
			}
		}
	}

	// 0 から各頂点への最小コストを保存する配列
	minCosts := make([]int, nNodes)

	minCosts[0] = 0
	for i := 1; i < nNodes; i++ {
		minCosts[i] = BIG_COST
	}

	// 各頂点が調査済みかどうかを保持する配列
	checked := make([]bool, nNodes)

	// 最小コストのパスを高速に取得するためのヒープ。
	// コストが小さいものほどルートに来るようにする。
	heap := NewHeap(func(a, b Path) bool {
		return a.cost < b.cost
	})

	heap.insert(Path{node: 0, cost: 0})
	for heap.size > 0 {
		u := heap.extractMax()

		// 隣接行列を使っていた時とは違い、ヒープには
		// 同じノードへのパスが複数含まれうる。そのため既によりコストの低い
		// パスが見つかっている場合は無視する。
		if minCosts[u.node] < u.cost {
			continue
		}

		checked[u.node] = true

		for _, v := range graph[u.node] {
			cost := v.cost + u.cost
			if !checked[v.node] && cost < minCosts[v.node] {
				minCosts[v.node] = cost
				heap.insert(Path{node: v.node, cost: cost})
			}
		}
	}

	w := bufio.NewWriter(os.Stdout)
	for i, cost := range minCosts {
		fmt.Fprintf(w, "%d %d\n", i, cost)
	}
	w.Flush()
}

func scanInt(sc *bufio.Scanner) int {
	sc.Scan()
	v, _ := strconv.Atoi(sc.Text())
	return v
}

// --- From ALDS1_9_C: Priority Queue

type Heap struct {
	size   int
	heap   []Path
	isHigh func(a, b Path) bool
}

func NewHeap(isHigh func(a, b Path) bool) Heap {
	heap := make([]Path, 1) // 先頭は不使用
	return Heap{size: 0, heap: heap, isHigh: isHigh}
}

func (h *Heap) insert(v Path) {
	h.size += 1
	if h.size > len(h.heap)-1 {
		h.heap = append(h.heap, v)
	} else {
		h.heap[h.size] = v
	}

	for i := h.size; i > 1; {
		parent := i / 2
		if h.isHigh(h.heap[parent], h.heap[i]) {
			break
		}
		h.heap[i], h.heap[parent] = h.heap[parent], h.heap[i]
		i = parent
	}
}

func (h *Heap) extractMax() Path {
	if h.size <= 0 {
		panic("cannot extract from empty heap")
	}

	max := h.heap[1]
	h.heap[1] = h.heap[h.size]
	h.size -= 1
	h.maxHeapify(1)

	return max
}

func (h *Heap) maxHeapify(idx int) {
	left := idx * 2
	right := left + 1
	largest := idx

	if left <= h.size {
		if h.isHigh(h.heap[left], h.heap[idx]) {
			largest = left
		}
		if right <= h.size && h.isHigh(h.heap[right], h.heap[largest]) {
			largest = right
		}
	}

	if largest != idx {
		h.heap[idx], h.heap[largest] = h.heap[largest], h.heap[idx]
		h.maxHeapify(largest)
	}
}

Python: import heapq


def dijkstra(adj_list, n):
    dist = [float("inf") for i in range(n)]
    visited = [False for _ in range(n)]
    parent = [-1 for _ in range(n)]
    start = 0
    dist[start] = 0
    dist_heap = []  # 距離が最小のノードをすぐに探せるようにするために使う。次のノードの候補を入れる。
    heapq.heappush(dist_heap, (dist[start], start))

    while len(dist_heap) > 0:
        cost, start = heapq.heappop(dist_heap)  # 一番近いノードがスタート地点となる
        visited[start] = True
        if dist[start] < cost:  # heapのコストが最短でなければ、distを更新する必要はない
            continue
        for end, weight in adj_list[start]:
            # startから出ているノードの距離を計算してheapqに入れる
            if not visited[end] and dist[start] + weight < dist[end]:
                dist[end] = dist[start] + weight
                parent[end] = start
                heapq.heappush(dist_heap, (dist[end], end))

    return parent, dist


def main():
    n = int(input())
    adj_list = []
    for _ in range(n):
        row = []
        line = input().split()
        dim = int(line[1])
        for i in range(dim):
            row.append((int(line[2 + i * 2]), int(line[2 + i * 2 + 1])))  # 番号, 重み
        adj_list.append(row)
    _, dist = dijkstra(adj_list, n)
    for i in range(n):
        print("{} {}".format(i, dist[i]))


if __name__ == "__main__":
    main()

Python: # -*- coding: utf-8 -*-
from heapq import heappop, heappush

N = int(input())
INF = 1 << 12
adj = [[] for _ in range(N)]

for n in range(N):
    inp = tuple(map(int, input().split()))
    adj[n] = list(zip(inp[2::2], inp[3::2]))

def dijkstra():
    d = [INF for n in range(N)]
    d[0] = 0
    heap = [[0, 0]]
    while len(heap):
        pcost, p = heappop(heap)
    
        for v, c in adj[p]:
            new_cost = d[p] + c
            if new_cost < d[v]:
                d[v] = new_cost
                heappush(heap, [new_cost, v])
    for n in range(N):
        print("{} {}".format(n, d[n]))

dijkstra()

Python: n = int(input())
G = [[-1 for i in range(n)] for j in range(n)]
d = [999999 for i in range(n)]
  
for i in range(n):
    v = input().split()
    for j in range(int(v[1])):
        G[int(v[0])][int(v[2+2*j])] = int(v[3+2*j])

d = [999999] * n
flag = [0] * n
d[0] = 0
while True:
    v = -1
    for j in range(n):
        if flag[j] != 1 and (v == -1 or d[j] < d[v]):
            v = j
    if v == -1:
        break
    flag[v] = 1
    for j in range(n):
        if G[v][j] == -1: continue
        d[j] = min(d[j], d[v] + G[v][j])

for i in range(n):
    print(str(i) + " " + str(d[i]))

Python: V=int(input())

G=[[] for i in range(V)]
d=[1001001001 for i in range(V)]

import heapq

def dijkstra(s):
    q=[]
    d[s]=0
    heapq.heappush(q,(0, s))
    
    while(len(q)):
        print(q)
        p=heapq.heappop(q)
        v=p[1]
        if d[v]<p[0]:
            continue
        for e in G[v]:
            if 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 in range(V):
    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])