Go: // ダイクストラのアルゴリズム
package main

import (
	"bufio"
	"fmt"
	"log"
	"math"
	"os"
	"strconv"
	"strings"
)

type color int

const (
	white color = iota // 未訪問
	mst                // MSTとして確定
)

// 頂点
type node struct {
	num     int         // 頂点の番号
	weights map[int]int // 重みMAP
	parent  *node       // MSTへの重み最小の親
	sum     int         // 始点からの距離
	color   color
}

func (p *node) getMinToMst() int {
	if p.parent == nil {
		return math.MaxInt32
	}
	return p.weights[p.parent.num]
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	n := eGetInt(scanner)

	nodes := make([]*node, n)
	for i := 0; i < n; i++ {
		weights := eAtoi((strings.Fields(eGetline(scanner))))
		v := &node{weights[0], make(map[int]int, weights[1]), nil, 0, white}
		for j := 0; j < weights[1]; j++ {
			k := weights[j*2+2] // 相手の頂点名
			w := weights[j*2+3] // 重み
			v.weights[k] = w
		}
		nodes[i] = v
	}

	// 初回はnode[0]がMSTに入るように
	nodes[0].parent = nodes[0]

	for { // 全部チェックするまで

		// どの頂点を新たにMSTに取り込むか

		var minNode *node
		min := math.MaxInt32
		for _, v := range nodes {
			if v.color == mst {
				continue
			}
			if v.getMinToMst() < min {
				min = v.getMinToMst()
				minNode = v
			}
		}
		if minNode == nil {
			// すべて完了している.
			break
		}

		// MSTに追加する頂点決定
		minNode.color = mst
		// 自分の親の合計値と合算する
		minNode.sum = minNode.parent.sum + min

		// MSTに属していない頂点それぞれについて,MSTとの最小の重みの距離を加算
		for _, v := range nodes {
			if v.color == mst {
				continue
			}
			w, ok := v.weights[minNode.num]
			if !ok {
				// minNodeと接してない
				continue
			}

			if w < v.getMinToMst() {
				// minNodeへの距離がもっとも重みが少ないので親を変更
				v.parent = minNode
			}
		}
	}

	for i, v := range nodes {
		fmt.Printf("%d %d\n", i, v.sum)
	}
}

func eGetInt(scanner *bufio.Scanner) int {
	t := eAtoi(strings.Fields(eGetline(scanner)))
	return t[0]
}

func eGetline(p *bufio.Scanner) string {
	if !p.Scan() {
		if err := p.Err(); err != nil {
			log.Fatal(err.Error())
		}
		return ""
	}
	return p.Text()
}

func eAtoi(s []string) []int {
	ints := make([]int, len(s))
	var err error
	for i, e := range s {
		ints[i], err = strconv.Atoi(e)
		if err != nil {
			log.Fatal(err.Error())
		}
	}
	return ints
}

Python: inf = float("inf")


class Node():

    def __init__(self, _id):
        self.id = _id
        self.d = inf
        self.pi = None
        self.color = 0
        self.adj = {}

    def input_data(self, data):
        k = data[0]
        for i in range(k):
            self.adj[G[data[2 * i + 1]]] = data[2 * i + 2]

    def __hash__(self):
        return hash(self.id)

def dijkstra():
    while True:
        mincost = inf
        for i in G:
            if i.color != 1 and i.d < mincost:
                mincost = i.d
                u = i
        if mincost == inf:
            break
        u.color = 1
        for v in u.adj.keys():
            if v.color != 1 and u.d + u.adj[v] < v.d:
                v.pi = u
                v.d = u.d + u.adj[v]

if __name__ == "__main__":
    n = int(input())
    G = [Node(i) for i in range(n)]
    for _ in range(n):
        data = [int(i) for i in input().split()]
        G[data[0]].input_data(data[1:])
        if data[0] == 0:
            G[data[0]].d = 0
    dijkstra()
    [print(i.id, i.d) for i in G]

Python: #!/usr/bin/env python3
import sys
import heapq
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

n=int(input())
G=[[] for i in range(n)]
for _ in range(n):
    inp = list(map(int,input().split()))
    u,k=inp[:2]
    for i in range(k):
        G[u].append((inp[2+2*i],inp[3+2*i]))

def disktra(g,s):
    n=len(g)
    dist = [inf]*n
    dist[s] = 0
    hq=[]
    heapq.heappush(hq,(dist[s],s))
    while hq:
        cost,u =heapq.heappop(hq)
        if dist[u] < cost:
            continue
        for v,c in g[u]:
            if dist[v] <= dist[u] +c:
                continue
            dist[v] = dist[u] + c
            heapq.heappush(hq,(dist[v],v))
    return dist

d=disktra(G,0)
for i in range(n):
    print(i,d[i])

Python: # Single Source Shortest Path 1
INF = 10**10
N = int(input())
W = [[INF]*(N) for _ in [0]*(N)]

for _ in [0]*N:
    v, k, *A = map(int, input().split())
    for u, c in zip(*[iter(A)]*2):
        W[v][u] = c

S = set()
d = [INF]*N

d[0] = 0
while len(S) < N:
    dmin = INF
    v = -1
    for i in range(N):
        if i not in S and d[i] < dmin:
            dmin = d[i]
            v = i

    S.add(v)
    for u, w in enumerate(W[v]):
        if d[v]+w < d[u]:
            d[u] = d[v]+w

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

Python: import heapq
N=int(input())
ad_li=[[]for i in range(N)]
for i in range(N):
    nums=list(map(int,input().split()))
    f=nums[0]
    for j in range(nums[1]):
        t=nums[j*2+2]
        c=nums[j*2+3]
        ad_li[f].append([t,c])

memo=[1E18 for i in range(N)]
memo[0]=0
qu=[]
heapq.heappush(qu,(0,0))
while len(qu)!=0:
    atop=heapq.heappop(qu)
    for ne in ad_li[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: INF = float('inf')


def dijkstra(source):
    distance[source] = 0
    parent[source] = -1

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

        if mincost == INF:
            break

        color[u] = 'black'

        for v in range(n):
            if color[v] != 'black' and adjMat[u][v] != INF:
                if distance[u] + adjMat[u][v] < distance[v]:
                    distance[v] = distance[u] + adjMat[u][v]
                    parent[v] = u
                    color[v] = 'gray'


n = int(input())
color = ['white'] * n
parent = [-1] * n
distance = [INF] * n

adjMat = [[INF] * n for _ in range(n)]
for i in range(n):
    inputList = list(map(int, input().split()))
    adjRow = inputList[0::2][1:]
    weightRow = inputList[1::2][1:]
    for v, weight in zip(adjRow, weightRow):
        adjMat[i][v] = weight

dijkstra(0)

for index, distance in enumerate(distance):
    print(('{} {}').format(index, distance))

Python: import sys
input = sys.stdin.readline

INF = 10**9
WHITE = -100
GRAY = -1000
BLACK = -10000

def main():
	m = int(input().strip())
	s = [[-1] * m for _ in range(m)]
	for i in range(m):
		l = list(map(int, input().strip().split()))
		for j in range(l[1]):
			s[i][l[2 + 2 * j]] = l[3 + 2 * j]
	color = [WHITE] * m
	d = [INF] * m
	p = [-1] * m

	d[0] = 0
	# for i in range(m):
	# 	print(s[i])
	color[0] = BLACK
	u = 0
	while True:
		for i in range(m):
			if color[i] != BLACK and s[u][i] != -1:
				if d[u] + s[u][i] < d[i]:
					d[i] = d[u] + s[u][i]
					p[i] = u
		mincost = INF
		for i in range(m):
			if color[i] != BLACK and d[i] < mincost:
				mincost = d[i]
				u = i
		if mincost == INF:
			break
		color[u] = BLACK
	for i in range(m):
		print("{} {}".format(i, d[i]))


if __name__ == '__main__':
	main()