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

class VCost:
    def __init__(self, v, cost):
        self.v_n = v
        self.cost = cost
    def __lt__(self, other):
        return self.cost < other.cost
    def __gt__(self, other):
        return self.cost > other.cost

adj = [[VCost(int(v), int(c)) for v, c in zip(x.split()[2::2], x.split()[3::2])] for x in f_i]

import heapq

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

    distance[0] = 0
    heapq.heappush(PQ, VCost(0, 0))
    
    while PQ:
        uc = heapq.heappop(PQ)
        u = uc.v_n

        if uc.cost > distance[uc.v_n]:
            continue

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

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


dijkstra()

Python: import sys
readline = sys.stdin.readline
from heapq import heapify, heappush, heappop
INF = float("inf")
def MAIN():
    n = int(input())
    adj = [[]] * n
    for _ in range(0, n):
        U = list(map(int, input().split()))
        adj[U[0]] = zip(U[2::2], U[3::2])
    def dijkstra():
        d = [INF] * n
        d[0] = 0
        hq = [(0, 0)]
        while hq:
            u = heappop(hq)[1]
            for v, c in adj[u]:
                alt = d[u] + c
                if d[v] > alt:
                    d[v] = alt
                    heappush(hq, (alt, v))
        print("\n".join(f"{i} {c}" for i, c in enumerate(d)))
    dijkstra()
MAIN()

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

N = int(input())
INF = float("inf")
costs = {n: INF for n in range(N)}
costs[0] = 0
graph = [{} for _ in range(N)]

unsearched = list(range(N))

for n in range(N):
    inp = tuple(map(int, input().split()))
    assert n == inp[0]
    for i in range(inp[1]):
        graph[n][inp[2*i+2]] = inp[2*i+3]

heap = [[0, 0]]
while len(unsearched) > 1:
    if len(heap):
        _, p = heappop(heap)
        unsearched.remove(p)
    heap = []
    for g in graph[p].keys():
        if g in unsearched:
            new_cost = costs[p] + graph[p][g]
            if new_cost < costs[g]:
                costs[g] = new_cost
            heappush(heap, [new_cost, g])
        else:
            pass

for n in range(N):
    print("{} {}".format(n, costs[n]))

Python: import heapq

class ShortestPath:
    def __init__(self, V, E, start, INF = float('inf')):
        self.V = V
        self.E = E 
        self.dijkstra(start, INF)

    def dijkstra(self, start, INF):
        que = list()
        self.distance = [INF] * self.V
        self.prev = [-1] * self.V
        self.distance[start] = 0
        heapq.heappush(que, (0, start))

        while len(que) > 0:
            dist, fr = heapq.heappop(que)
            if self.distance[fr] < dist:
                continue
            for to, cost in self.E[fr]:
                if self.distance[fr] + cost < self.distance[to]:
                    self.distance[to] = self.distance[fr] + cost
                    heapq.heappush(que, (self.distance[to], to))
                    self.prev[to] = fr 


V = int(input())
edge = [[] for _ in range(V)]
for _ in range(V):
    u, _, *e = map(int, input().split())
    for t, d in zip(e[::2], e[1::2]):
        edge[u].append((t, d))

sp = ShortestPath(V, edge, 0)
for i, d in enumerate(sp.distance):
    print(i, d)

Python: import heapq


def dijkstra(n):
    inf=float("inf")
    color=["white" for _ in range(n)]
    D=[inf for _ in range(n)]
    P=[0 for _ in range(n)]
    M=[[] for _ in range(n)]

    for i in range(n):
        A=list(map(int, input().split()))
        for j in range(A[1]):
            M[i].append([A[2*(j+1)],A[2*(j+1)+1]])

    D[0]=0
    P[0]=-1

    H=[(0,0)]
    heapq.heapify(H)

    while len(H)>=1:
        u=heapq.heappop(H)[1]
        if color[u]=="black":continue
        color[u]="black"

        V=[(i,j) for i,j in M[u] if color[i]!="black"]
        while len(V)!=0:
            for i,j in V:
                if D[u]+j<D[i]:
                    D[i]=D[u]+j
                    P[i]=u
                    color[i]="gray"
                    heapq.heappush(H,(D[i],i))
            break

    return D


for i,j in enumerate(dijkstra(int(input()))):
    print(i,j)

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, u = heapq.heappop(PQ)

        if uc > distance[u]:
            continue

        isVisited[u] = True
        
        for vc, v in adj[u]:
            if isVisited[v] == True:
                continue
            
            t_cost = distance[u] + vc
            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()