Go: package main

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

var sc = bufio.NewScanner(os.Stdin)

const T = 10000000

var n int
var A [101][101]int

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}
func Shortestsearch() {
	var Minimum int
	var d, color [100]int
	var u int

	for i := 0; i < n; i++ {
		d[i] = T
		color[i] = 0
	}

	d[0] = 0
	color[0] = 1

	for {
		Minimum = T
		u = -1
		for i := 0; i < n; i++ {
			if Minimum > d[i] && color[i] != 2 {
				u = i
				Minimum = d[i]
			}
		}
		if u == -1 {
			break
		}
		color[u] = 2
		for j := 0; j < n; j++ {
			if color[j] != 2 && A[u][j] != T {
				if d[j] > d[u]+A[u][j] {
					d[j] = d[u] + A[u][j]
					color[j] = 1
				}
			}
		}
	}
	for i := 0; i < n; i++ {
		fmt.Printf("%d %d\n", i, d[i])
	}
}
func main() {
	sc.Split(bufio.ScanWords)
	n = nextInt()

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			A[i][j] = T
		}
	}
	for i := 0; i < n; i++ {
		u := nextInt()
		k := nextInt()
		for j := 0; j < k; j++ {
			v := nextInt()
			c := nextInt()
			A[u][v] = c
		}
	}
	Shortestsearch()
}

Python: rootList = [-1 for i in range(n)]
parent = [0 for i in range(n)]
lenList = [0 for i in range(n)]

def getRoot(x):
    r = rootList[x]
    if r < 0:
        rootList[x] = x
    elif r != x:
        rootList[x] = getRoot(r)
    return rootList[x]


edgeList.sort(key=lambda x: x[0])
flag = True
while flag:
    flag = False
    for e in edgeList:
        if e[2] == 0:
            continue
        x = getRoot(e[1])
        y = getRoot(e[2])
        if x == 0 != y:
            parent[e[2]] = e[1]
            lenList[e[2]] += lenList[e[1]] + e[0]
            rootList[y] = 0
            flag = True
            break

for i, j in zip(range(n), lenList):
    print(i, j)

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]}")