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: #!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint


def main():
    num = int(stdin.readline())

    L = []
    for _ in xrange(num):
        L.append([int(s) for s in stdin.readline().split()])

    weight = [maxint] * num
    index = 0
    rearch = {0}
    total_c = 0

    while maxint not in rearch:
        min_v = min_c = maxint
        Li = L[index]
        for i in xrange(Li[1]):
            v = Li[i*2+2]
            if v in rearch:
                continue
            c = Li[i*2+3]
            weight[v] = min(weight[v], c + total_c)
            if min_c > c:
                min_c = c
                min_v = v
        index = min_v
        rearch.add(min_v)
        total_c += min_c

    weight[0] = 0
    for i, d in enumerate(weight):
        print(i, d)


main()

Python: INFINITY = 10 ** 10
WHITE = 0
GRAY = 1
BLACK = 2


n = int(input())
M = [[INFINITY] * n for _ in range(n)]

for _ in range(n):
    u, k, *list_num = map(int, input().split())

    for i in range(0, k * 2, 2):
        M[u][list_num[i]] = list_num[i + 1]

d = [INFINITY] * n

def dijkstra():
    color = [WHITE] * n
    p = [None] * n

    d[0] = 0
    p[0] = -1

    while True:
        cost_min = INFINITY
        for i in range(n):
            if color[i] != BLACK and d[i] < cost_min:
                cost_min = d[i]
                top_now = i

        if cost_min == INFINITY:
            break
    
        color[top_now] = BLACK

        for v in range(n):
            if color[v] == BLACK or M[top_now][v] == INFINITY:
                continue

            cost_now = d[top_now] + M[top_now][v]
            if cost_now < d[v]:
                d[v] = cost_now
                p[v] = top_now
                color[v] = GRAY


dijkstra()

for i, cost in enumerate(d):
    print(i, cost)

Python: n = int(input())
C = [[] for _ in range(n)]
for _ in range(n):
    tmp = list(map(int,input().split()))
    for i in range(1,tmp[1]+1):
        C[tmp[0]].append(tuple(tmp[2*i:2*i+2]))


def dijkstra(start = 0):
    INF = 100000000
    d = [INF]*n
    visited = [False]*n

    d[start] = 0
    visited[start] = True
    S = {start}

    while 1:
        for s in S:
            for adj_weight in C[s]:
                if visited[adj_weight[0]] == False:
                    d[adj_weight[0]] = min(d[s] + adj_weight[1],d[adj_weight[0]])
        
        min_d = INF
        min_node = -1
        for i in range(n):
            if visited[i] == False and d[i] < min_d:
                min_d = d[i]
                min_node = i
        if min_node == -1:
            break
        else:
            visited[min_node] = True
            S.add(min_node)
    return d

ans = dijkstra()
for i in range(n):
    print("{} {}".format(i,ans[i]))

Python: def relax(u, v, w):
    if D[u] + w < D[v]:
        D[v] = D[u] + w
        P[v] = u

INF = float('inf')
N = int(input())
D = [INF for i in range(N)]
P = [None for i in range(N)]
C = ['w' for i in range(N)]
D[0] = 0

G = [[INF for j in range(N)] for i in range(N)]
for i in range(N):
    x = list(map(int, input().split()))
    g = x[2:]
    for j, n in enumerate(g):
        if j % 2 == 0:
            G[i][n] = g[j + 1]


while True:
    mincost = INF
    u = -1
    for i in range(N):
        if C[i] != 'b' and D[i] < mincost:
            mincost = D[i]
            u = i
    if u == -1:
        break
    C[u] = 'b'
    for v, w in enumerate(G[u]):
        if w != INF and C[v] != 'b':
            relax(u, v, w)
            C[v] = 'g'

for i, d in enumerate(D):
    print('{0} {1}'.format(i, d))

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

def main():
    INF = float('inf')
    V = int(input())
    dist = [INF] * V
    visited = [False] * V
    graph = [None] + [deque() for i in range(V-1)]
    
    q = []
    tmp = list(map(int, input().split()))
    for i in range(tmp[1]): heappush(q, (tmp[2+2*i+1], tmp[2+2*i]))
        
    for i in range(1, V):
        tmp = list(map(int, input().split()))
        
        for j in range(tmp[1]):
            graph[i].append((tmp[2+2*j+1], tmp[2+2*j]))
        
    dist[0], visited[0] = 0, True
        
    while q:
        cost, v = heappop(q)
        if visited[v]: continue
    
        visited[v] = True
        dist[v] = cost
        
        for c, u in graph[v]:
            if visited[u] or dist[u] < cost + c: continue
            heappush(q, (cost+c, u))
    
    for i in range(V): print(i, dist[i])
        
if __name__ == '__main__':
    main()

Python: n = int(input())
g = [[2**64]*n 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][v] = c

'''
ダイクストラ法による単一始点最短経路
'''
d = [2**64]*n
d[0] = 0

s = []
v = [i for i in range(n)]
while len(s) < n:
    c, u = 2**32, -1
    for vv in v:
        if d[vv] < c:
            c, u = d[vv], vv
    s.append(u)
    v.remove(u)
    for i, c in enumerate(g[u]):
        if i in v and d[u]+g[u][i] < d[i]:
            d[i] = d[u]+g[u][i]

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