Go: package main

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

const BIG_COST = 200000

const (
	ST_NOT_YET = iota
	ST_JOINED
)

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	nNodes := scanInt(sc)

	costs := make([][]int, nNodes)
	graph := make([][]int, nNodes)

	states := make([]int, nNodes)
	costSums := make([]int, nNodes)

	for i := 0; i < nNodes; i++ {
		costs[i] = make([]int, nNodes)
		costSums[i] = BIG_COST
	}

	for i := 0; i < nNodes; i++ {
		u := scanInt(sc)
		k := scanInt(sc)
		graph[u] = make([]int, k)
		for d := 0; d < k; d++ {
			v := scanInt(sc)
			graph[u][d] = v
			costs[u][v] = scanInt(sc)
		}
	}

	costSums[0] = 0
	for {
		minCost := BIG_COST
		var u int

		for i, cost := range costSums {
			if states[i] != ST_JOINED && cost < minCost {
				minCost = cost
				u = i
			}
		}

		if minCost == BIG_COST {
			break
		}

		states[u] = ST_JOINED

		for _, v := range graph[u] {
			cost := minCost + costs[u][v]
			if cost < costSums[v] {
				costSums[v] = cost
			}
		}
	}

	w := bufio.NewWriter(os.Stdout)
	for i, cost := range costSums {
		fmt.Fprintf(w, "%d %d\n", i, cost)
	}
	w.Flush()
}

func scanInt(sc *bufio.Scanner) int {
	sc.Scan()
	v, _ := strconv.Atoi(sc.Text())
	return v
}

Python: trial = int(input())
graph = []
for t in range(trial):
    graph.append([int(n) for n in input().split(" ")])
root = []
ans = []
stack = [[0,0]]
cnt = 0
while len(stack) > 0:
    index,out = stack[0][0],stack[0][1]
    print(index,out,stack,graph)
    for get in range(graph[index][1]):
        if graph[index][get*2 + 2] not in root:
            stack.append([graph[index][get*2 +2],graph[index][get*2 +3] + out ])
    if stack[0][0] not in root:
        root.append(stack[0][0])
        ans.append([stack[0][0],stack[0][1]])
    stack.pop(0)
    stack = sorted(stack,key=lambda x:x[1])
ans = sorted(ans,key=lambda x:x[0])
for a in ans:
    print(a)

Python: #!/usr/bin/python3
n = int(input())
inf = 100 * 100000

M = [[inf for i in range(n)] for j in range(n)]

for i in range(n):
    L = list(map(int, input().split()))
    u = L[0]
    k = L[1]
    v = L[2::2]
    c = L[3::2]
    for j in range(k):
        M[u][v[j]] = M[v[j]][u] = c[j]

S = set()
V = set(range(n))
S.add(0)
d = [inf for i in range(n)]
d[0] = 0
count = 0
while len(V - S) != 0 and count < 10:
    T = V - S
    nd = [inf for i in range(n)]
    for s in S:
        for m, c in enumerate(M[s]):
            if d[s] + c < nd[m] and m in T:
                nd[m] = d[s] + c

    min_nd = min(nd)
    u = nd.index(min_nd)
    S.add(u)
    d[u] = min_nd

    count += 1

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

Python: n = int(input())
M = {}
for _ in range(n):
    u, k, *line = map(int, input().split())
    tmp = []
    for i in range(k):
        v, w = line[2*i:2*i+2]
        tmp.append((v, w))
    M[u] = tmp

INF = 10**10
WHITE = 0
GREY = 1
BLACK = 2
d = [INF] * n
color = [WHITE] * n
p = [-1] * n


def dijkstra():
    d[0] = 0
    p[0] = -1

    while True:
        mincost = INF
        for i in range(0, n):
            if color[i] != BLACK and d[i] < mincost:
                mincost = d[i]
                u = i

        if mincost == INF:
            break

        color[u] = BLACK

        for v, w in M[u]:
            if color[v] != BLACK:
                if d[u]+w < d[v]:
                    d[v] = d[u]+w
                    p[v] = u


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

Python: N = int(input())
color = ["w" for _ in range(N)]
d = [float("inf") for _ in range(N)]
p = [-1 for _ in range(N)]

# Make M
M = [[-1]*N for _ in range(N)]
for i in range(N):
    input_list = list(map(int, input().split()))
    ii = input_list.pop(0)
    k = input_list.pop(0)
    jj = 0
    while jj <= 2*k - 2:
        M[ii][input_list[jj]] = input_list[jj+1]
        jj += 2

d[0] = 0
while True:
    mincost = float("inf")
    for i in range(N):
        if color[i] != "b" and d[i] < mincost:
            mincost = d[i]
            u = i
    
    if mincost == float("inf"):
        break
    color[u] = "b"

    for v in range(N):
        if color[v] != "b" and M[u][v] != -1:
            if d[v] > M[u][v] + d[u]:
                d[v] = M[u][v] + d[u]
                p[v] = u
                
for i in range(N):
    print("{} {}".format(i, d[i]))

Python: INF = 1000000


def diikstraMethd(G, s):
    # ?????????
    n = len(G)
    # White:0 Gyay:1 Black:2
    color = [0 for _ in range(n)]
    d = [INF for _ in range(n)]
    p = [None for _ in range(n)]

    d[s] = 0

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

        if mincost == INF: break

        color[u] = 2

        for v in range(n):
            if color[v] != 2 and M[u][v] != INF:
                if d[u] + M[u][v] < d[v]:
                    d[v] = d[u] + M[u][v]
                    p[v] = u
                    color[u] = 1

    return d


if __name__ == '__main__':
    n = int(input())
    M = [[INF for _ in range(n)] for i in range(n)]
    for _ in range(n):
        tmp = list(map(int, input().split()))
        u = tmp.pop(0)
        k = tmp.pop(0)
        for _ in range(k):
            v = tmp.pop(0)
            c = tmp.pop(0)
            M[u][v] = c
    d = diikstraMethd(M, 0)

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.discard(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: import sys
from heapq import *

MAX_INT= 10 ** 10

n = int(input())
adj_list = []

for _ in range(n):
  commands = sys.stdin.readline().split()
  lst = [ commands[i:i+2] for i in range(2, len(commands), 2)]
  adj_list.append(lst)

def dijkstra():
  # initialization
  visited = [False] * n
  dist_arr = [MAX_INT] * n
  pq = []
  prev = [None] * n

  # append 0 to pqs
  pq = [(0, 0)]
  dist_arr[0] = 0

  while len(pq) > 0:
    dist, idx = heappop(pq)
    visited[idx] = True

    # updating current values in dist
    for edge in adj_list[idx]:
      cur_idx, cur_dist = [ int(e) for e in edge]
      if visited[cur_idx]: continue

      new_dist = dist + cur_dist

      if new_dist < dist_arr[cur_idx]:
        dist_arr[cur_idx] = new_dist
        heappush(pq, (dist_arr[cur_idx], cur_idx))

  return dist_arr

distArr = dijkstra()
for i in range(n):
  print(i, distArr[i])

Python: inf = float('inf')
n = int(input())
g = []
for i in range(n):
    line = list(map(int, input().split()))
    k = line[1]
    c = [inf] * n
    for j in range(k):
        v = line[2 + 2 * j]
        c[v] = line[3 + 2 * j]
    g.append(c)

distance = [inf] * n
distance[0] = 0
visited = [False] * n
current = 0

while not all(visited):
    visited[current] = True
    min_i = 0
    min_d = inf
    for i in range(n):
        if not visited[i]:
            if distance[current] + g[current][i] < distance[i]:
                distance[i] = distance[current] + g[current][i]
            if distance[i] < min_d:
                min_i = i
                min_d = distance[i]
    current = min_i

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