Go: package main

import (
	"bufio"
	"bytes"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
)

const (
	INFTY = 1 << 21
	NIL   = -1
)

const (
	WHITE = iota
	GRAY
	BLACK
)

type Graph [][]int

func (g *Graph) dikstra(n int) string {
	var (
		u, minv = 0, 0
	)

	d := make([]int, n)
	color := make([]int, n)

	for i := 0; i < n; i++ {
		d[i] = INFTY
		color[i] = WHITE
	}
	d[0] = 0
	color[0] = GRAY

	for {
		minv = INFTY
		u = -1
		for i := 0; i < n; i++ {
			if minv > d[i] && color[i] != BLACK {
				u = i
				minv = d[i]
			}
		}

		if u == -1 {
			break
		}

		color[u] = BLACK
		for v := 0; v < n; v++ {
			if color[v] != BLACK && (*g)[u][v] != INFTY {
				if d[v] > d[u]+(*g)[u][v] {
					d[v] = d[u] + (*g)[u][v]
					color[v] = GRAY
				}
			}
		}
	}

	var out bytes.Buffer
	for i := 0; i < n; i++ {
		out.WriteString(fmt.Sprintf("%d ", i))
		if d[i] == INFTY {
			out.WriteString(fmt.Sprintf("%d\n", -1))
			continue
		}
		out.WriteString(fmt.Sprintf("%d\n", d[i]))
	}

	return strings.TrimRight(out.String(), "\n")
}

func answer(reader io.Reader) string {
	sc := bufio.NewScanner(reader)
	sc.Split(bufio.ScanWords)

	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())

	g := make(Graph, n)
	for i := 0; i < n; i++ {
		g[i] = make([]int, n)
		for j := 0; j < n; j++ {
			g[i][j] = INFTY
		}
	}

	for i := 0; i < n; i++ {
		sc.Scan()
		u, _ := strconv.Atoi(sc.Text())
		sc.Scan()
		k, _ := strconv.Atoi(sc.Text())

		for j := 0; j < k; j++ {
			sc.Scan()
			v, _ := strconv.Atoi(sc.Text())
			sc.Scan()
			c, _ := strconv.Atoi(sc.Text())

			g[u][v] = c
		}
	}

	return g.dikstra(n)
}

func main() {
	fmt.Println(answer(os.Stdin))
}

Python: from collections import namedtuple
import heapq

Edge = namedtuple('Edge', ('fr', 'to', 'cost'))
inf = int(1e9)


def bellman_ford(n, start, edges):
    dists = [inf for _ in range(n)]
    dists[start] = 0
    while True:
        updated = False
        for e in edges:
            if dists[e.fr] != inf and dists[e.fr] + e.cost < dists[e.to]:
                updated = True
                dists[e.to] = dists[e.fr] + e.cost

        if not updated:
            break

    return dists


def dijkstra(n, costs):
    dists = [inf for _ in range(n)]
    dists[0] = 0

    queue = []
    for (i, d) in enumerate(dists):
        heapq.heappush(queue, (d, i))

    while len(queue) > 0:
        d, i = heapq.heappop(queue)
        if d > dists[i]:
            continue

        for v in range(n):
            if v == i or costs[i][v] == inf:
                continue

            if dists[i] + costs[i][v] < dists[v]:
                dists[v] = dists[i] + costs[i][v]
                heapq.heappush(queue, (dists[v], v))

    return dists


def warshall_floyd(n, costs):
    dists = [[costs[i][j] if i != j else 0 for i in range(n)] for j in range(n)]

    for k in range(n):
        for i in range(n):
            for j in range(n):
                dists[i][j] = min(dists[i][j], dists[i][k] + dists[k][j])

    return dists


n = int(input())

m = [[inf for _ in range(n)] for _ in range(n)]
es = []
for i in range(n):
    fs = list(map(int, input().split()))
    ne = fs[1]
    for j in range(ne):
        v = fs[2+2*j]
        c = fs[2+2*j+1]
        m[i][v] = c
        es.append(Edge(i, v, c))


# d = bellman_ford(n, 0, es)
# d = dijkstra(n, m)
d = warshall_floyd(n, m)
for (i, di) in enumerate(d[0]):
    print(i, di)

Python: n = int(input())

graph = [[] for i in range(n)]

for i in range(n):
    a = list(map(int, input().split()))
    for j in range(a[1]):
        graph[a[0]].append(a[2+j*2:4+j*2])  #[頂点, cost]

memo = [10**10 for i in range(n)]
memo[0] = 0

import heapq
q = []
heapq.heappush(q, (0, 0))   #(それまでのcost, 頂点)
while len(q) != 0:
    top = heapq.heappop(q)
    for g in graph[top[1]]:
        cost = top[0] + g[1]
        if memo[g[0]] > cost:
            memo[g[0]] = cost
            heapq.heappush(q, (cost, g[0]))

for i in range(n):
    print(i, memo[i])

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))