Go: package main

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

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

var infty = 1000000000

type DirectedGraphNodeID int

type DirectedGraphNode struct {
	key         DirectedGraphNodeID
	adjacents   []*DirectedGraphNode
	costs       []int
	distance    int
	predecessor *DirectedGraphNode
}

func newDirectedGraph(nNodes int) *DirectedGraph {
	graph := DirectedGraph{}
	graph.nodes = make([]*DirectedGraphNode, nNodes)
	for i := 0; i < nNodes; i++ {
		node := DirectedGraphNode{}
		node.key = DirectedGraphNodeID(i)
		node.distance = infty
		graph.nodes[i] = &node
	}
	return &graph
}

type DirectedGraph struct {
	nodes []*DirectedGraphNode
}

func (g *DirectedGraph) setAdjacency(i, j DirectedGraphNodeID, cost int) {
	g.nodes[i].adjacents = append(g.nodes[i].adjacents, g.nodes[j])
	g.nodes[i].costs = append(g.nodes[i].costs, cost)
}

func (g *DirectedGraph) print() {
	for i := 0; i < len(g.nodes); i++ {
		node := g.nodes[i]
		key := node.key
		strings := []string{strconv.Itoa(int(key)), strconv.Itoa(node.distance)}
		for j := 0; j < len(node.adjacents); j++ {
			nodeJ := fmt.Sprintf("(%v, %v)", node.adjacents[j].key, node.costs[j])
			strings = append(strings, nodeJ)
		}
		fmt.Printf("%v\n", strings)
	}
}

func (g *DirectedGraph) relaxEdge(l, r *DirectedGraphNode, w int) {
	if r.distance > l.distance+w {
		// fmt.Printf("%v -> %v, %v\n", l.key, r.key, l.distance+w)
		r.distance = l.distance + w
		r.predecessor = l
	}
}

func main() {
	scanner.Split(bufio.ScanWords)

	nNodes := nextInt()
	graph := newDirectedGraph(nNodes)

	for i := 0; i < nNodes; i++ {
		iNode := DirectedGraphNodeID(nextInt())
		nAdjacent := nextInt()
		for j := 0; j < nAdjacent; j++ {
			jNode := DirectedGraphNodeID(nextInt())
			cost := nextInt()
			graph.setAdjacency(iNode, jNode, cost)
		}
	}

	graph.nodes[0].distance = 0
	for iNode := 0; iNode < nNodes; iNode++ {
		for iLeft := 0; iLeft < len(graph.nodes); iLeft++ {
			nodeLeft := graph.nodes[iLeft]
			for iRight := 0; iRight < len(nodeLeft.adjacents); iRight++ {
				nodeRight := nodeLeft.adjacents[iRight]
				cost := nodeLeft.costs[iRight]
				graph.relaxEdge(nodeLeft, nodeRight, cost)
			}
		}
	}

	// graph.print()

	for iNode := 0; iNode < len(graph.nodes); iNode++ {
		node := graph.nodes[iNode]
		fmt.Println(node.key, node.distance)
	}
}

Python: # 単一視点最短経路, Dijkstra(ダイクストラ)のアルゴリズム
from collections import deque

n = int(input())
# グラフの作成
INF = float('inf')
M = [[INF]*n for _ in range(n)]
d = [INF]*n
for _ in range(n):
    u, k, *v = map(int, input().split())
    if k == 0:
        continue
    cnt = 0
    for _ in range(k):
        M[u][v[cnt]] = v[cnt+1]
        cnt += 2

# アルゴリズム部分
def djikstra(n, M, d):
    d[0] = 0
    color = ['W']*n
    color[0] = 'G'
    while True:
        mincost = INF
        u = -1
        for i in range(n):
            if mincost > d[i] and color[i] != 'B':
                u = i
                mincost = d[i]
        if u == -1:
            break

        color[u] = 'B'
        for v in range(n):
            if color[v] != 'B' and M[u][v] != INF:
                if d[v] > d[u]+M[u][v]:
                    d[v] = d[u]+M[u][v]
                    color[v] = 'G'
    return d

D = djikstra(n, M, d)
for i, c in enumerate(D):
    print(i, c)

Python: import io, sys, itertools
f = sys.stdin


def take2(iterable):
    i = iter(iterable)
    while True:
        yield next(i), next(i)


n = int(f.readline())
adj =[[(v, c) for v, c in take2(map(int, f.readline().split()[2:]))] for _ in range(n)]
d = [100000 * 100 + 1] * n

d[0] = 0
def search(parent, children):
    global d
    for v, c in children:
        if d[v] > d[parent] + c:
            d[v] = d[parent] + c
            search(v, adj[v])
    
search(0, adj[0])
    
for i in range(n):
    print(i, d[i])

Python: import sys
input = sys.stdin.readline

INF = 100100

def dijkstra(M: list, u: int = 0) -> list:
    global N
    d = [INF] * N
    d[u] = 0
    visited = [False] * N
    while True:
        mincost = INF
        for i in range(N):
            if not visited[i] and d[i] < mincost:
                mincost = d[i]
                u = i
        if mincost == INF:
            return d
        visited[u] = True
        for v in range(N):
            if not visited[v]:
                if d[u] + M[u][v] < d[v] :
                    d[v] = d[u] + M[u][v]


def main():
    global N
    N = int(input())
    M = [[INF]*N for _ in range(N)]
    for _ in range(N):
        A = list(map(int, input().split()))
        u = A[0]
        k = A[1]
        for i in range(k):
            v = A[2+2*i]
            c = A[3+2*i]
            M[u][v] = c
    d = dijkstra(M)
    for i, di in enumerate(d):
        print(i, di)

if __name__ == '__main__': main()

Python: # -*- coding: utf-8 -*-

N = int(input())
INF = float("inf")
adj = [[INF]*N for _ in range(N)]

for n in range(N):
    inp = tuple(map(int, input().split()))
    assert n == inp[0]
    for i in range(inp[1]):
        adj[inp[0]][inp[2*i+2]] = inp[2*i+3]

not_MST = list(range(1, N))
MST = [0]
costs = {n:INF for n in range(N)}
costs[0] = 0

for n in range(1, N):
    if adj[0][n] < INF:
        costs[n] = adj[0][n]

m = 0

while len(not_MST):
    tmp_min = INF
    tmp_idx = -1
    
    for n in not_MST:
        if costs[m] + adj[m][n] < costs[n]:
            costs[n] = costs[m] + adj[m][n]
    
    for m in not_MST:
        if costs[m] < tmp_min:
            tmp_min = costs[m]
            tmp_idx = m
    
    MST.append(tmp_idx)
    not_MST.remove(tmp_idx)
    m = tmp_idx

for n in range(N):
    print("{} {}".format(n, costs[n]))

Python: n = int(input())

adj = [[100001 for j in range(n)] for i in range(n)]

for u in range(n):
    x = list(map(int, input().split()))
    for v, c in zip(x[2::2], x[3::2]):
        adj[u][v] = c

unvisited = [v for v in range(n)]

distance = [9900001] * n


def dijkstra(s):
    distance[s] = 0

    while True:
        mincost = 9900001
        for i in unvisited:
            if distance[i] < mincost:
                mincost = distance[i]
                u = i

        if mincost == 9900001:
            break

        unvisited.remove(u)

        for v in unvisited:
            weight_uv = adj[u][v]
            if weight_uv != 100001:
                t_d = distance[u] + weight_uv
                if t_d < distance[v]:
                    distance[v] = t_d



dijkstra(0)

for v, d in enumerate(distance):
    print(v, d)

Python: n = int(input())
edgeList = []

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

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)