Go: package main

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

const NIL = -1

type Node struct {
	id     int
	weight int
}

func init() {
	sc.Split(bufio.ScanWords)
}

type NodeHeap []Node

func (h NodeHeap) Len() int           { return len(h) }
func (h NodeHeap) Less(i, j int) bool { return h[i].weight < h[j].weight }
func (h NodeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *NodeHeap) Push(x interface{}) {
	*h = append(*h, x.(Node))
}

func (h *NodeHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	num, _ := strconv.Atoi(scanString())
	return num
}

func scanString() string {
	sc.Scan()
	return sc.Text()
}

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	n := scanInt()

	list := make([][]int, n)
	weight := make([]int, n)
	for i := range list {
		list[i] = make([]int, n)
		weight[i] = NIL
		for j := range list[i] {
			list[i][j] = NIL
		}
	}

	for i := 0; i < n; i++ {
		u := scanInt()
		k := scanInt()
		for j := 0; j < k; j++ {
			v := scanInt()
			w := scanInt()
			list[u][v] = w
		}
	}

	start := Node{id: 0, weight: 0}
	h := &NodeHeap{start}
	heap.Init(h)

	for h.Len() > 0 {
		node := heap.Pop(h).(Node)
		if weight[node.id] != NIL {
			continue
		}
		weight[node.id] = node.weight

		for i, w := range list[node.id] {
			if w == NIL {
				continue
			}
			heap.Push(h, Node{id: i, weight: w + node.weight})
		}
	}

	w := bufio.NewWriter(os.Stdout)
	for i := 0; i < n; i++ {
		fmt.Fprint(w, i)
		fmt.Fprint(w, " ")
		fmt.Fprint(w, weight[i])
		fmt.Fprintln(w)
	}
	w.Flush()
}

Python: if __name__ == '__main__':
    from sys import stdin
    input = stdin.readline

    import heapq
    from copy import deepcopy

    INFTY = 2**21
    WHITE = 0
    GRAY = 1
    BLACK = 2

    n = int(input())

    M = [[INFTY]*n for _ in range(n)]

    for _ in range(n):
        u, k, *vc = map(int, input().split())
        cv = [0]*k
        for v, c in zip(vc[::2], vc[1::2]):
            M[u][v] = c
            
    def dijkstra():
        d = [INFTY]*n
        color = [WHITE]*n

        d[0] = 0
        color[0] = GRAY
        while True:
            minv = INFTY
            u = -1
            for i in range(n):
                if minv > d[i] and color[i] != BLACK:
                    u = i
                    minv = d[i]

            if u == -1:
                break
            color[u] = BLACK
            for v in range(n):
                if color[v] != BLACK and M[u][v] != INFTY:
                    if d[v] > d[u]+M[u][v]:
                        d[v] = d[u] + M[u][v]
                        color[v] = GRAY

        for i in range(n):
            print(str(i) + ' ' + str(-1 if d[i] == INFTY else d[i]))

    dijkstra()

    """

    nodes = [[] for _ in range(n)]

    for _ in range(n):
        u, k, *vc = map(int, input().split())
        cv = [0]*k
        for i, (v, c) in enumerate(zip(vc[::2], vc[1::2])):
            cv[i] = (c, v)
        nodes[u] = cv

    d = [INFTY]*n
    d[0] = 0

    d_node = nodes[0]
    heapq.heapify(d_node)

    visited = [False]*n
    visited[0] = True

    while d_node:
        min_c, min_v = heapq.heappop(d_node)
        if visited[min_v]:
            continue
        visited[min_v] = True
        d[min_v] = min_c
        for c, v in nodes[min_v]:
            heapq.heappush(d_node, (min_c+c, v))

    for u, dist in enumerate(d):
        print(str(u) + ' ' + str(dist))
    """

Python: #!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
5
0 3 2 3 3 1 1 2
1 2 0 2 3 4
2 3 0 3 3 1 4 1
3 4 2 1 0 1 1 4 4 3
4 2 2 1 3 3

output:
0 0
1 2
2 2
3 1
4 3
"""

import sys

WHITE, GRAY, BLACK = 0, 1, 2
D_MAX = int(1e7 + 1)


def generate_adj_matrix(v_info):
    for each in v_info:
        v_index, v_adj_length, *v_adj_list = map(int, each)
        # assert len(v_adj_list) == v_adj_length * 2
        for pair in zip(v_adj_list[::2], v_adj_list[1::2]):
            init_adj_matrix[v_index][pair[0]] = pair[1]

    return init_adj_matrix


def dijkstra_path():
    path_list[0] = 0

    while True:
        min_cost = D_MAX
        current_vertex_index = None
        for i in range(vertices_num):
            if color[i] is not BLACK and path_list[i] < min_cost:
                min_cost = path_list[i]
                current_vertex_index = i

        if min_cost == D_MAX:
            break

        color[current_vertex_index] = BLACK
        current_vertex_index_info = adj_table[current_vertex_index]
        for adj_vertex_index in current_vertex_index_info.keys():
            current_adj_weight = current_vertex_index_info.get(adj_vertex_index)
            if color[adj_vertex_index] is not BLACK:
                alt_path = path_list[current_vertex_index] + current_adj_weight
                if alt_path < path_list[adj_vertex_index]:
                    # update path_list
                    path_list[adj_vertex_index] = alt_path
                    parent_list[adj_vertex_index] = current_vertex_index
                    color[adj_vertex_index] = GRAY

    return path_list


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices_num = int(_input[0])
    init_vertices_table = (map(lambda x: x.split(), _input[1:]))
    # assert len(init_vertices_table) == vertices_num

    parent_list, path_list = [-1] * vertices_num, [D_MAX] * vertices_num
    color = [WHITE] * vertices_num
    init_adj_matrix = tuple(dict() for _ in range(vertices_num))
    adj_table = generate_adj_matrix(init_vertices_table)
    ans = dijkstra_path()
    for j in range(vertices_num):
        print(j, ans[j])

Python: trial = int(input())
graph = []
for t in range(trial):
    graph.append([int(n) for n in input().split(" ")])
root = []
ans = []
stack = [[0,0]]
cnt = 0
while len(stack) > 0:
    index,out = stack[0][0],stack[0][1]
    for get in range(graph[index][1]):
        if graph[index][get*2 + 2] not in root:
            stack.append([graph[index][get*2 +2],graph[index][get*2 +3] + out ])
    if stack[0][0] not in root:
        root.append(stack[0][0])
        ans.append([stack[0][0],stack[0][1]])
    stack.pop(0)
    stack = sorted(stack,key=lambda x:x[1])
ans = sorted(ans,key=lambda x:x[0])
for a in ans:
    print(a)

Python: INF = float('inf')


def dijkstra(source):
    distance[source] = 0
    parent[source] = -1

    while True:
        mincost = INF
        for i in range(n):
            if color[i] != 'black' and distance[i] < mincost:
                mincost = distance[i]
                u = i

        if mincost == INF:
            break

        color[u] = 'black'

        for v in range(n):
            if color[v] != 'black' and adjMat[u][v] != INF:
                if distance[u] + adjMat[u][v] < distance[v]:
                    distance[v] = distance[u] + adjMat[u][v]
                    parent[v] = u
                    color[v] = 'gray'


n = int(input())
color = ['white'] * n
parent = [-1] * n
distance = [INF] * n

adjMat = [[INF] * n for _ in range(n)]
for i in range(n):
    inputList = list(map(int, input().split()))
    adjRow = inputList[0::2][1:]
    weightRow = inputList[1::2][1:]
    for v, weight in zip(adjRow, weightRow):
        adjMat[i][v] = weight

dijkstra(0)

for index, distance in enumerate(distance):
    print('{} {}').format(index, distance)