Go: package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const BIG_COST = 200000

const (
	ST_NOT_YET = iota
	ST_JOINED
)

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

	nNodes := scanInt(sc)

	costs := make([][]int, nNodes)
	graph := make([][]int, nNodes)

	states := make([]int, nNodes)
	costSums := make([]int, nNodes)

	for i := 0; i < nNodes; i++ {
		costs[i] = make([]int, nNodes)
		costSums[i] = BIG_COST
	}

	for i := 0; i < nNodes; i++ {
		u := scanInt(sc)
		k := scanInt(sc)
		graph[u] = make([]int, k)
		for d := 0; d < k; d++ {
			v := scanInt(sc)
			graph[u][d] = v
			costs[u][v] = scanInt(sc)
		}
	}

	costSums[0] = 0
	for {
		minCost := BIG_COST
		var u int

		for i, cost := range costSums {
			if states[i] != ST_JOINED && cost < minCost {
				minCost = cost
				u = i
			}
		}

		if minCost == BIG_COST {
			break
		}

		states[u] = ST_JOINED

		for _, v := range graph[u] {
			cost := minCost + costs[u][v]
			if cost < costSums[v] {
				costSums[v] = cost
			}
		}
	}

	w := bufio.NewWriter(os.Stdout)
	for i, cost := range costSums {
		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
}

Python: """Shortest Path"""

import sys
import os
import pprint

#fd = os.open('ALDS1_12_B.txt', os.O_RDONLY)
#os.dup2(fd, sys.stdin.fileno())

level = True
def debug(v):
    if level:
        print(v)

n = int(input())
INF = 100001
W = [[INF for j in range(n)] for i in range(n)]

for _ in range(n):
    l = list(map(int, input().split()))
    node_index = l[0]
    num = l[1]
    data = l[2:]
    for i in range(num):
        node = data[i*2]
        weight = data[i*2+1]
        W[node_index][node] = weight

d = [INF] * n
visited = [False] * n
parent = [None] * n

# root
d[0] = 0

while True:
    min_dist = INF
    min_index = None
    for i in range(n):
        if not visited[i] and d[i] < min_dist:
            min_dist = d[i]
            min_index = i

    if min_index is None:
        break

    # accept
    visited[min_index] = True

    for i in range(n):
        if not visited[i] and d[i] > d[min_index] + W[min_index][i]:
            d[i] = d[min_index] + W[min_index][i]
            parent[i] = min_index
for i in range(len(d)):
    s = '{} {}'.format(i, d[i])
    print(s)

Python: import heapq

n = int(input())
edges = [None] * n
for _ in range(n):
    l = list(map(int, input().split()))
    edges[l[0]] = set((c, j) for j, c in (l[i:i + 2] for i in range(2, l[1] * 2 + 2, 2)))

min_costs = [0] * n
visited = [False] * n
visited[0] = True
queue = list(edges[0])
heapq.heapify(queue)

while queue:
    total_cost, vertex = heapq.heappop(queue)
    if visited[vertex]:
        continue
    visited[vertex] = True
    min_costs[vertex] = total_cost
    for cost, vertex2 in edges[vertex]:
        if not visited[vertex2]:
            heapq.heappush(queue, (total_cost + cost, vertex2))

for r in enumerate(min_costs):
    print(*r)

Python: n = int(input())

INF = 2147483647
M = [[INF for j in range(n)] for i in range(n)]
check, dist = [0 for i in range(n)], [INF for i in range(n)]


def dijkstra(s):
    p = [-1 for i in range(n)]
    dist[s] = 0

    while True:
        min_cost = INF
        for i in range(n):
            if check[i] != 2 and dist[i] < min_cost:
                min_cost = dist[i]
                u = i

        if min_cost == INF:
            break

        check[u] = 2

        for v in range(n):
            if check[v] != 2 and M[u][v] != INF:
                if dist[u] + M[u][v] < dist[v]:
                    dist[v], p[v] = dist[u] + M[u][v], u
                    check[v] = 1


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

    dijkstra(0)

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


if __name__ == '__main__':
    main()

Python: def createMatrix():
    matrix = [[INFTY] * n for i in range(n)]
    for i in range(n):
        u, k, *v = map(int, input().split())
        for j in range(0, k*2, 2):
            matrix[i][v[j]] = v[j+1]
    return matrix

def dijkstra():
    d[0] = 0
    p[0] = -1

    while True:
        mincost = INFTY
        # cost が最小の node を選択
        for i in range(n):
            if status[i] != VISITED and d[i] < mincost:
                mincost = d[i]
                u = i

        if mincost == INFTY:
            break

        status[u] = VISITED

        # u と v をつなぐ edge のうち最小の経路のコストの合計に更新
        for v in range(n):
            if status[v] != VISITED and matrix[u][v] != INFTY:
                if d[u] + matrix[u][v] < d[v]:
                    d[v] = d[u] + matrix[u][v]
                    p[v] = u
                    status[v] = VISITING

import sys
# sys.stdin = open('input.txt')

n = int(input())
NOT_VISITED = 0 # WHITE
VISITING = 1 # GRAY
VISITED = 2 # BLACK
INFTY = 10**21

matrix = createMatrix()
status =  [NOT_VISITED] * n
d = [INFTY] * n
p = [-1] * n

dijkstra()

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

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
import heapq as hp

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


def generate_adj_matrix(v_info):
    for v_detail in v_info:
        v_index = int(v_detail[0])
        v_adj_length = int(v_detail[1])
        v_adj_list = v_detail[2:]
        # assert len(v_adj_list) == v_adj_length * 2
        for j in range(0, v_adj_length * 2, 2):
            init_adj_matrix[v_index][v_adj_list[j]] = int(v_adj_list[j + 1])

    return init_adj_matrix


def dijkstra_path():
    # path search init
    start_vertex_index = 0
    path_list[start_vertex_index] = 0
    path_heap = []
    # heapq: compare by tuple[0]
    hp.heappush(path_heap, (path_list[start_vertex_index], start_vertex_index))
    while len(path_heap) >= 1:
        current_vertex = hp.heappop(path_heap)[1]

        color[current_vertex] = BLACK

        for adj_vertex in range(vertices_num):
            current_adj_weight = adj_matrix[current_vertex].get(str(adj_vertex), -1)
            if current_adj_weight < 0:
                continue
            elif color[adj_vertex] is not BLACK:
                # d[u] + w[u,v]
                alt_path = path_list[current_vertex] + current_adj_weight
                if alt_path < path_list[adj_vertex]:
                    # update path_list
                    path_list[adj_vertex] = alt_path
                    # update heap
                    hp.heappush(path_heap, (alt_path, adj_vertex))
                    parent_list[adj_vertex] = current_vertex
                    color[adj_vertex] = GRAY

    return path_list


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices_num = int(_input[0])
    init_vertices_table = list(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_matrix = generate_adj_matrix(init_vertices_table)
    ans = dijkstra_path()
    for i, v in enumerate(ans):
        print(i, v)