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
import sys

input = sys.stdin.readline
INF = 100100100

class Info:
    def __init__(self, argNodeId, argSumCost):
        self.nodeId = argNodeId
        self.sumCost = argSumCost
    def __lt__(self, arg):
        return self.sumCost < arg.sumCost


class Edge:
    def __init__(self, argTo, argCost):
        self.to = argTo
        self.cost = argCost


def main():
    n = int(input())
    minDist = [INF] * n
    graph = [[] for _ in range(n)]
    for _ in range (n):
        u, k, *cv = map(int, input().split())
        for i in range(k):
            graph[u].append(Edge(cv[2 * i], cv[2*i + 1]))
    minDist[0] = 0
    Q = []
    heapq.heappush(Q, Info(0, 0))
    while len(Q) > 0:
        u = heapq.heappop(Q)
        if u.sumCost > minDist[u.nodeId]:
            continue
        for edge in graph[u.nodeId]:
            if minDist[edge.to] > u.sumCost + edge.cost:
                minDist[edge.to] = u.sumCost + edge.cost
                heapq.heappush(Q, Info(edge.to, minDist[edge.to]))
    for i in range(n):
        print('{} {}'.format(i, minDist[i]))


if __name__ == '__main__': main()

Python: from heapq import*
I=float("inf")
def m():
 n=int(input())
 A=[[]]*n
 for _ in range(n):
  e=list(map(int,input().split()))
  A[e[0]]=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))
 for i in range(n):print(i,d[i])
m()

Python: import sys
from heapq import *

MAX_INT= 10 ** 10

n = int(input())
adj_list = []

for _ in range(n):
  commands = sys.stdin.readline().split()
  lst = [ commands[i:i+2] for i in range(2, len(commands), 2)]
  adj_list.append(lst)

def dijkstra():
  # initialization
  visited = [False] * n
  dist_arr = [MAX_INT] * n
  pq = []
  prev = [None] * n

  # append 0 to pqs
  pq = [(0, 0)]
  dist_arr[0] = 0

  while len(pq) > 0:
    dist, idx = heappop(pq)
    visited[idx] = True

    # updating current values in dist
    for edge in adj_list[idx]:
      cur_idx, cur_dist = [ int(e) for e in edge]
      if visited[cur_idx]: continue

      new_dist = dist + cur_dist

      if new_dist < dist_arr[cur_idx]:
        dist_arr[cur_idx] = new_dist
        heappush(pq, (dist_arr[cur_idx], cur_idx))

  return dist_arr

distArr = dijkstra()
for i in range(n):
  print(i, distArr[i])

Python: from heapq import heappop, heappush
from collections import defaultdict


class Dijkstra:
    """Graph input:
    {
    node:{node:cost,node:cost...},
    node:{node:cost,node:cost...},
    ...
    }
    """

    def __init__(self, graph: dict, N: int):
        self.graph = graph
        self.costs = [float("inf")] * N

    def calculate(self, start):
        queue = list()

        # step1: push the start point into the priority queue
        self.costs[start] = 0
        heappush(queue, (0, start))  # (cost,node)

        while queue:
            # step2: get the minimum cost node from unfixed node and fix the cost
            cost_from_start, min_node = heappop(queue)

            # step3: update the direct connected nodes
            for link, cost in self.graph[min_node].items():
                if cost_from_start + cost < self.costs[link]:
                    self.costs[link] = cost_from_start + cost
                    heappush(queue, (self.costs[link], link))

        return self.costs


n = int(input())
graph = defaultdict(dict)

for _ in range(n):
    data = [int(i) for i in input().split()]
    u = data[0]
    count = data[1]
    for j in range(1, count + 1):
        v = data[2 * j]
        w = data[2 * j + 1]
        graph[u][v] = w

dijkstra = Dijkstra(graph, n)
costs = dijkstra.calculate(0)

for i in range(n):
    print(i, costs[i])