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: V=int(input())
inf=10**9
cost=[[inf]*V for _ in range(V)]
for i in range(V):
    l=list(map(int,input().split()))
    for j in range(l[1]):
        v,c=l[2*j+2],l[2*j+3]
        cost[i][v]=c
d=[inf]*V
d[0]=0
used=[0]*V

while True:
    v=-1
    for u in range(V):
        if (not used[u] and (v==-1 or d[u]<d[v])):
            v=u
    if v==-1:
        break
    used[v]=1
    for u in range(V):
        d[u]=min(d[u],d[v]+cost[v][u])

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

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]]:
        next_cost = atop[0] + ne[1]
        if(memo[ne[0]] > next_cost):
            memo[ne[0]] = next_cost
            heapq.heappush(qu, (next_cost,ne[0]))
for i in range(N):
    print(i, memo[i])

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
    weight[0] = 0
    V = set(xrange(1, num))
    index = 0

    while V:
        Li = L[index]
        for i in xrange(Li[1]):
            v = Li[i*2+2]
            if v not in V:
                continue
            c = Li[i*2+3]
            weight[v] = min(weight[v], c + weight[index])

        index = min(V, key=lambda i: weight[i])
        V.remove(index)

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


main()

Python: def dijkstra(n):
    distance_list[0] = 0
    while True:
        min_distance = 10**9
        u = -1
        for i in range(n):
            distance = distance_list[i]
            if flag_list[i] < 2 and distance < min_distance:
                min_distance = distance
                u = i
        if u == -1:
            break
        flag_list[u] = 2
        for v in range(n):
            edge = m_list[u][v]
            if flag_list[v] < 2 and -1 < edge:
                if distance_list[u] + edge < distance_list[v]:
                    distance_list[v] = distance_list[u] + edge
                    p[v] = u
                    flag_list[v] = 1


if __name__ == "__main__":
    n = int(input())
    m_list = [[-1]*n  for _ in range(n)]
    for i in range(n):
        in_list = list(map(int, input().split()))
        adj_num = in_list[1]
        tmp = []
        if adj_num > 0:
            for j in range(adj_num):
                m_list[i][in_list[j*2+2]] = in_list[j*2+3]

    flag_list = [0]*n # 0: 未到達, 1: 処理中, 2: 完了
    distance_list = [10**9]*n
    p = [-1]*n
    dijkstra(n)
    for i, d in enumerate(distance_list):
        print(i, d)

Python: def diikstraMethd(G, s):
    # ?????????
    n = len(G)
    # White:0 Gyay:1 Black:2
    color = [0 for _ in range(n)]
    d = [INF for _ in range(n)]
    p = [None for _ in range(n)]

    d[s] = 0

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

        if mincost == INF: break

        color[u] = 2

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

    return d

if __name__ == '__main__':
    n = int(input())
    M = [[INF for _ in range(n)] for i in range(n)]
    for _ in range(n):
        tmp = list(map(int, input().split()))
        u = tmp.pop(0)
        k = tmp.pop(0)
        for _ in range(k):
            v = tmp.pop(0)
            c = tmp.pop(0)
            M[u][v] = c
    d = diikstraMethd(M, 0)

    for i in range(n):
        print('{0} {1}'.format(i, d[i]))

Python: n = int(input())
G = [[-1] * n] * n
d = [0] * n
 
for i in range(n):
    v = map(int, input().split())
    for j in range(v[1]):
        G[v[0]][v[2+2*j]] = int(v[3+2*j])
 
flag = [0] * n
tn = [1]
r = 0
while True:
    for i in range(n):
        if flag[i] == 0 and i in tn:
            flag[i] = 1
            d[i] = r
            for j in range(n):
                if G[i][j] != -1 and flag[j] == 0:
                    tn.append(j)
    if len(tn) == n:
        break
    r += 1
 
for i in range(1, n+1):
    print(str(i) + " " + str(d[i]))

Python: n = int(raw_input())
G = [[-1] * n] * n
d = [0] * n
 
for i in range(n):
    v = map(int, raw_input().split())
    for j in range(v[1]):
        G[v[0]][v[2+2*j]] = int(v[3+2*j])
 
flag = [0] * n
tn = [0]
r = 0
while True:
    for i in range(n):
        if flag[i] == 0 and i in tn:
            flag[i] = 1
            d[i] = r
            for j in range(n):
                if G[i][j] != -1 and flag[j] == 0:
                    tn.append(j)
    if len(tn) == n:
        break
    r += 1
 
for i in range(n):
    print(str(i) + " " + str(d[i]))

Python: import sys
input = sys.stdin.readline


# import heapq
import heapq

# graph: 隣接リスト (頂点、距離）の順に格納
# start: 始点 (0-index)
# n: 頂点数
# memo[t]: startからtまでの最短距離
# return memo

def dijkstra(graph, start, n):
    INF = float('inf')
    memo = [INF] * n
    memo[start] = 0
    q = [(0, start)]

    while q:
        dist, ver = heapq.heappop(q)
        if memo[ver] < dist:
            continue
        for next_ver, next_dist in graph[ver]:
            if memo[next_ver] > dist + next_dist:
                memo[next_ver] = dist + next_dist
                heapq.heappush(q, (dist + next_dist, next_ver))

    return memo

n = int(input())
graph = [[] for i in range(n)]
for i in range(n):
    info = list(map(int, input().split()))
    for j in range(info[1]):
        graph[info[0]].append((info[j*2 + 2], info[j*2 + 3]))

memo = dijkstra(graph, 0, n)
for i, d in enumerate(memo):
    print(i, d)