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 sys

f_i = sys.stdin

n = int(f_i.readline())

adj = [[]] * n
for x in f_i:
    x = list(map(int, x.split()))
    adj[x[0]] = [c_v for c_v in zip(x[3::2], x[2::2])]

import heapq

def dijkstra():
    PQ = [(0, 0)]
    isVisited = [False] * n
    distance = [999900001] * n

    distance[0] = 0
    
    while PQ:
        uc = heapq.heappop(PQ)
        u = uc[1]

        if uc[0] > distance[u]:
            continue

        isVisited[u] = True
        
        for c, v in adj[u]:
            if isVisited[v] == True:
                continue
            t_cost = distance[u] + c
            if t_cost < distance[v]:
                distance[v] = t_cost
                heapq.heappush(PQ, (t_cost, v))

    for v, d in enumerate(distance):
        print(v, d)


dijkstra()

Python: #coding:utf-8
inf = 1000000
n = int(input())
M = [[inf for i in range(n)] for j in range(n)]
vwMtrx = []
for i in range(n):
    data = list(map(int,input().split()))
    u = data[0]
    k = data[1]
    col = []
    for j in range(0,2*k,2):
        v, w = data[j+2], data[j+3]
        M[u][v] = w
        col.append([v,w])
    vwMtrx.append(col)

def dijkstra(s):
    color = ["white" for i in range(n)]
    d = [inf for i in range(n)]
    p = [-1 for i in range(n)]
    d[s] = 0
    Q = [[s,0]]
    while Q != []:
        u = min(Q, key=lambda x:x[1])
        Q = [List for List in Q if List != u]
        u = u[0]
        color[u] = "black"

        vwList = vwMtrx[u]
        
        for vw in vwList:
            v,w = vw[0],vw[1]
            if color[v] != "black" and M[u][v] != inf:
                if d[u] + M[u][v] < d[v]:
                    d[v] = d[u] + M[u][v]
                    p[v] = u
                    color[v] = "gray"
                    Q.append([v, d[v]])

    return d

dList = dijkstra(0)
for i, d in enumerate(dList):
    print(i,d)

Python: import heapq

n = int(input())
maxim = 100010
adj = [[] for _ in range(n)]

for _ in range(n):
    u, k, *v = map(int, input().split())
    if k == 0:
        adj[u].append((0,0))
    for i in range(k):
        adj[u].append((v[i*2+1], v[i*2]))

def dijkstra():
    global adj
    PQ = []
    heapq.heapify(PQ)
    color = ['W']*n
    d = [maxim]*n
    d[0] = 0
    heapq.heappush(PQ, (0, 0))
    color[0] = 'G'

    while PQ:
        f = heapq.heappop(PQ)
        u = f[1]
        color[u] = 'B'
        if d[u] < f[0]*-1:
            continue
        for j in range(len(adj[u])):
            v = adj[u][j][1]
            if color[v] == 'B':
                continue
            if d[v] > d[u]+adj[u][j][0]:
                d[v] = d[u]+adj[u][j][0]
                heapq.heappush(PQ, (d[v], v))
                color[v] = 'G'
    return d

D = dijkstra()
for i, x in enumerate(D):
    print(i, x)

Python: import heapq as hp

INF = 1000000

def diikstraMethd(G, s):
    # ?????????
    n = len(G)
    d = [INF for _ in range(n)]
    d[s] = 0
    PQ = [(d[s], s)]

    while PQ:
        u = hp.heappop(PQ)[1]
        for v, c in G[u]:
            alt = d[u] + c
            if d[v] > alt:
                d[v] = alt
                hp.heappush(PQ, (alt, v))

    return d


if __name__ == '__main__':
    n = int(input())
    G = [ [] for _ in range(n)]
    for _ in range(n):
        tmp = list(map(int, input().split()))
        u = tmp.pop(0)
        k = tmp.pop(0)
        for i in range(k):
            v = tmp.pop(0)
            c = tmp.pop(0)
            G[u].append((v, c))

    d = diikstraMethd(G, 0)

    for i in range(n):
        print('{0} {1}'.format(i, d[i]))

Python: import heapq
WHITE = 0
GRAY = 1
BLACK = 2
INFTY = 10**13
def dijkstra(s):
    color = [WHITE for i in range(N)]
    d = [INFTY for i in range(N)]
    d[s] = 0
    pq = []
    heapq.heappush(pq, (0, s))

    while len(pq) != 0:
        u = heapq.heappop(pq)[1]
        color[u] = BLACK

        for v, c in VC[u]:
            if color[v] != BLACK:
                if d[u] + c < d[v]:
                    d[v] = d[u] + c
                    color[v] = GRAY
                    heapq.heappush(pq, (d[v], v))

    return d

N = int(input())
VC = [[] for i in range(N)]
for i in range(N):
    ukvc = list(map(int, input().split()))
    u, k, vc = ukvc[0], ukvc[1], ukvc[2:]
    for v, c in zip(vc[0::2], vc[1::2]):
        VC[u].append([v, c])

d = dijkstra(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])