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: #!/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):
        it = iter(int(s) for s in stdin.readline().split()[1:])
        L.append([(next(it), next(it)) for _ in xrange(next(it))])

    weight = [maxint] * num
    weight[0] = 0
    V = set(xrange(1, num))
    index = 0

    while V:
        for v, cost in L[index]:
            if v not in V:
                continue
            weight[v] = min(weight[v], cost + weight[index])

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

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


main()

Python: INFTY = 1 << 21
WHITE = 0
GRAY = 1
BLACK = 2
 
n = int(input())
M = [list(map(int, input().split())) for i in range(n)]
 
d = [INFTY for i in range(n)]
color = [WHITE for i in range(n)]
 
for i in range(n):
    u = int(input())
    k = int(input())
    for j in range(k):
        v = int(input())
        c = int(input())
        M[u][v] = c
        
def dijkstra():
    global M, d, color
    d[0] = 0
    color[0] = GRAY
    while(1):
        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), (-1 if d[i] == INFTY else str(d[i])))
dijkstra()

Python: import queue

INFTY=1<<21

#ダイクストラ法
def dijkstra(n,EdgeMatrix):

    NodeList=queue.PriorityQueue() #探索対象の頂点
    Distance=[INFTY]*n #頂点0からの最短経路
    used=[False]*n #頂点の使用情報

    Distance[0]=0 #0から0までの距離は0
    used[0]=True #0から探索を始める
    LastNode=0 #最新の頂点
    count=1 #つないだ頂点の数

    while count<n:
        for i in range(n):
            #探索していない頂点へ距離の短い辺があればキューに追加
            if EdgeMatrix[LastNode][i]!=INFTY and used[i]==False:
                if Distance[i]>Distance[LastNode]+EdgeMatrix[LastNode][i]:
                    Distance[i]=Distance[LastNode]+EdgeMatrix[LastNode][i]
                    NodeList.put([Distance[i],i])

        #最も近い探索していない頂点
        while True:
            minNode=NodeList.get()
            if used[minNode[1]]==False:
                break

        LastNode=minNode[1] #最新の頂点を更新
        used[minNode[1]]=True #頂点の使用情報を更新
        count+=1 #つないだ頂点の数を更新

    return Distance

#入力
n=int(input())

#辺の隣接行列
EdgeMatrix=[[INFTY]*n for i in range(n)]
for i in range(n):
    l=(list(map(int,input().split())))
    for j in range(l[1]):
        EdgeMatrix[l[0]][l[2*j+2]]=l[2*j+3]

#頂点0からの最短経路
Distance=dijkstra(n,EdgeMatrix)

for node,distance in enumerate(Distance):
    print(node,distance)

Python: import sys
readline = sys.stdin.readline
from heapq import heapify, heappush, heappop
INF = float("inf")
def MAIN():
    n = int(input())
    adj = [[]] * n
    for _ in range(0, n):
        U = list(map(int, input().split()))
        adj[U[0]] = zip(U[2::2], U[3::2])
    def dijkstra():
        d = [0] + [INF] * (n - 1)
        hq = [(0, 0)]
        while hq:
            u = heappop(hq)[1]
            for v, c in adj[u]:
                alt = d[u] + c
                if d[v] > alt:
                    d[v] = alt
                    heappush(hq, (alt, v))
        print("\n".join(f"{i} {c}" for i, c in enumerate(d)))
    dijkstra()
MAIN()

Python: #coding:utf-8
def Dijkestra(G,n):
    d=[100000000000]*n
    pi=[None]*n
    d[0]=0
    C=[]
    for i in range(n):
        C.append(i)
    
    while len(C)!=0:
        u=C[0]
        for i in range(1,len(C)):
            if d[u]>d[i]:
                u=i
        C.remove(u)
        for i in range(len(G[u])):
            if G[u][i]==-1:
                continue
            elif d[i]>d[u]+G[u][i]:
                d[i]=d[u]+G[u][i]
                pi[i]=u
                        
    for i in range(n):
        print(i,d[i])
    

if __name__=="__main__":
    n=int(input())
    G=[]
    for i in range(n):
        a=[]
        ele=list(map(int,input().split()))
        k=ele[1]
        t=ele[2:]
        v=c=[]
        for j in range(k):
            v=v+[t[2*j]]
            c=c+[t[2*j+1]]
        for j in range(n):
            if j in v:
                a.append(c[v.index(j)])
            else:
                a.append(-1)
        G.append(a)
    Dijkestra(G,n)

Python: n = int(input())
E = [[] for i in range(n)]#[[]]*nだと同一アドレスの単一リストがコピーされる
lrg = 10**8
for i in range(n):
    inpt = list(map(int, input().split( )))
    for j in range(inpt[1]):
        E[inpt[0]].append(inpt[2*j+2:2*j+4])
    #print(inpt[0],E[inpt[0]],*inpt)

D = [lrg]*n
D[0] = 0

G =[0]

Prev = [-1]*n
cnt=0
while cnt < n:#len(D)<nでは制御できていない,Dは距離,Gは到達リスト
    for v in G:
        for [u,c] in E[v]:
            if D[u]>D[v]+c:
                #print("replaced")
                D[u] = D[v]+c
                Prev[u]=v
            if u not in G:
                G.append(u)
                #print("append",u)
    cnt+=1            
for v in G:
    for [u,c] in E[v]:
        if D[u]>D[v]+c:
            D[u] = D[v]+c
            Prev[u]=v
            
for i in range(n):
    print(i,D[i])

Python: rootList = [-1 for i in range(n)]
parent = [0 for i in range(n)]
lenList = [float("inf") for i in range(n)]
lenList[0] = 0
def getRoot(x):
    r = rootList[x]
    if r < 0:
        rootList[x] = x
    elif r != x:
        rootList[x] = getRoot(r)
    return rootList[x]

flag = True
while flag:
    flag = False
    edgeList.sort(key=lambda x: (x[0] + lenList[x[1]]))
    for e in edgeList:    # weight:e[0], e[1]->e[2]
        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)