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: # -*- coding: utf-8 -*-
from heapq import heappop, heappush


def dijkstra(edges, start, *, adj_matrix=False, default_value=float('inf')):
    '''
    Returns best costs to each node from 'start' node in the given graph.
    (Single Source Shortest Path - SSSP)

    If edges is given as an adjacency list including costs and destination nodes on possible edges, adj_matrix should be False(default), and it is generally when this functions works much faster.

    Note that costs in edges should follow the rules below
    1. The cost from a node itself should be 0,
    2. If there is no edge between nodes, the cost between them should be default_value
    3. The costs can't be negative

    # sample input when given as adjacency list (adj_matrix=False)
    edges = [[(1, 2), (2, 5), (3, 4)],         # node 0
             [(0, 2), (3, 3), (4, 6)],         # node 1
             [(0, 5), (3, 2), (5, 6)],         # node 2
             [(0, 4), (1, 3), (2, 2), (4, 2)], # node 3
             [(1, 6), (3, 2), (5, 4)],         # node 4
             [(2, 6), (4, 4)]]                 # node 5

    # sample input when given as adjacency matrix (adj_matrix=True)
    edges = [[0, 2, 5, 4, inf, inf],           # node 0
             [2, 0, inf, 3, 6, inf],           # node 1
             [5, inf, 0, 2, inf, 6],           # node 2
             [4, 3, 2, 0, 2, inf],             # node 3
             [inf, 6, inf, 2, 0, 4],           # node 4
             [inf, inf, 6, inf, 4, 0]]         # node 5
    '''

    n = len(edges)

    costs = [float('inf')] * n
    costs[start] = 0

    pq = [(0, start)]
    rem = n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) if adj_matrix else\
                    edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))

    return costs


def dijkstra_route(edges,
                   start,
                   goal,
                   *,
                   adj_matrix=False,
                   default_value=float('inf'),
                   verbose=False):
    '''
    Trys to find the best route to the 'goal' from the 'start'
    '''

    n = len(edges)

    costs = [float('inf')] * n
    costs[start] = 0
    pq = [(0, start)]
    rem = n - 1
    prevs = [-1 for _ in [None] * n]

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) if adj_matrix else\
                    edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))
                prevs[nxt_node] = tmp_node

    min_route = []
    prev = goal
    cnt = 0
    while prev != start:
        min_route.append(prev)
        prev = prevs[prev]

        cnt += 1
        if prev == -1 or cnt > n:
            raise NoRouteError(
                'There is no possible route in this graph \nedges: {} \nstart: {} \ngoal: {}'.
                format(edges, start, goal))

    else:
        min_route.append(prev)
    min_route = min_route[::-1]
    min_cost = costs[goal]

    if verbose:
        print('---route---')
        for node in min_route[:-1]:
            print('{} -> '.format(node), end='')
        else:
            print(min_route[-1])

        print('---distance---')
        print(min_cost)

    return costs, min_route


class NoRouteError(Exception):
    pass


if __name__ == '__main__':
    '''
    an example of using this function
    AIZU ONLINE JUDGE - ALDS_1_12_C
    '''

    n = int(input())
    edges = [[] for i in range(n)]
    for i in range(n):
        i, k, *kedges = map(int, input().split())
        for edge in zip(kedges[::2], kedges[1::2]):
            edges[i].append(edge)

    costs = dijkstra(edges, 0)
    for i, cost in enumerate(costs):
        print(i, cost)

Python: import heapq

N = int(input())
A = [[]for i in range(N)]

for i in range(N):
    u, k, *nums = list(map(int,input().split()))
    for j in range(k):
        t = nums[j*2]
        c = nums[j*2+1]
        A[u].append([t, c])

memo = [1E18] * N
memo[0] = 0
qu = []
heapq.heappush(qu, (0,0))
while len(qu) != 0:
    atop = heapq.heappop(qu)
    for ne in A[atop[1]]:
        x = ne[0]
        next_cost = atop[0] + ne[1]
        if(memo[x] > next_cost):
            memo[x] = next_cost
            heapq.heappush(qu, (next_cost, x))
for i in range(N):
    print(i, memo[i])