Go: package main

import (
	"fmt"
	"bufio"
	"os"
	"strconv"
	"container/heap"
)

type Node struct {
	Id int
	Dis int
}

type PriorityQueue []*Node

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].Dis < pq[j].Dis
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(*Node))
}

func (pq *PriorityQueue) Pop() interface{} {
	n := len(*pq)
	pop := (*pq)[n-1]
	*pq = (*pq)[0:n-1]
	return pop
}

func main() {
	var n int
	fmt.Scan(&n)

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

	g := make([][]int, n)
	c := make([][]int, n)
	pq := make(PriorityQueue, 0, n)
	d := make([]int, n)
	for i := 0; i < n; i++ {
		sc.Scan()
		u, _ := strconv.Atoi(sc.Text())
		sc.Scan()
		k, _ := strconv.Atoi(sc.Text())
		g[u] = make([]int, k)
		c[u] = make([]int, k)
		for j := 0; j < k; j++ {
			sc.Scan()
			g[u][j], _ = strconv.Atoi(sc.Text())
			sc.Scan()
			c[u][j], _ = strconv.Atoi(sc.Text())
		}

		if u == 0 {
			d[u] = 0
		} else {
			d[u] = 1 << 30
		}
		pq.Push(&Node{u, d[u]})
	}
	heap.Init(&pq)

	for pq.Len() > 0 {
		node := heap.Pop(&pq).(*Node)
		for i := 0; i < len(g[node.Id]); i++ {
			nextId := g[node.Id][i]
			nextDis := node.Dis + c[node.Id][i]
			if nextDis < d[nextId] {
				d[nextId] = nextDis
				heap.Push(&pq, &Node{nextId, nextDis})
			}
		}
	}

	wr := bufio.NewWriter(os.Stdout)
	for i := 0; i < n; i++ {
		wr.WriteString(strconv.Itoa(i))
		wr.WriteString(" ")
		wr.WriteString(strconv.Itoa(d[i]))
		wr.WriteString("\n")
	}
	wr.Flush()
}

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)

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], 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)

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], 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)

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

Python: from heapq import heappop, heappush

n = int(input())
g = [[] for i in range(n)]
for i in range(n):
    u, k, *l, = map(int, input().split())
    for j in range(k):
        v, c = l[j*2], l[j*2+1]
        g[u].append([v, c])

'''
ダイクストラ法による単一始点最短経路
二分ヒープ（優先度付きキュー）による高速化
'''
d = [2**64]*n
d[0] = 0
h = []
heappush(h, (0, 0))

m = [False]*n
while len(h) > 0:
    c, u = heappop(h)
    m[u] = True
    if d[u] < c:
        continue
    for gv, gc in g[u]:
        if not m[gv] and d[u]+gc < d[gv]:
            d[gv] = d[u]+gc
            heappush(h, (d[u]+gc, gv))

for i in range(n):
    print(f"{i} {d[i]}")