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



N = int(eval(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])))
# -*- coding: utf-8 -*-

from heapq import heappush, heappop



N = int(eval(input()))

INF = float("inf")

adj = []

for _ in range(N):

    inp = tuple(map(int, input().split()))

    adj.append(tuple(zip(inp[2::2], inp[3::2])))



checked = [False for _ in range(N)]

d = [float("inf") for _ in range(N)]

d[0] = 0



heap = [[0, 0]] # cost, vec



while heap:

    c, u = heappop(heap)

    if d[u] < c or checked[u]:

        continue

    for nu, nc in adj[u]:

        new_d = d[u] + nc

        if new_d < d[nu]:

            d[nu] = new_d

            heappush(heap, [d[nu], nu])

    checked[u] = True



for n in range(N):

    print(("{} {}".format(n, d[n])))
# -*- coding: utf-8 -*-
N = int(eval(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])))

# -*- coding: utf-8 -*-
from heapq import heappush, heappop

N = int(eval(input()))
INF = float("inf")
adj = []
for _ in range(N):
    inp = tuple(map(int, input().split()))
    adj.append(tuple(zip(inp[2::2], inp[3::2])))
checked = [False for _ in range(N)]
d = [float("inf") for _ in range(N)]
d[0] = 0
heap = [[0, 0]]  # cost, vec
while heap:
    c, u = heappop(heap)
    if d[u] < c or checked[u]:
        continue
    for nu, nc in adj[u]:
        new_d = d[u] + nc
        if new_d < d[nu]:
            d[nu] = new_d
            heappush(heap, [d[nu], nu])
    checked[u] = True
for n in range(N):
    print(("{} {}".format(n, d[n])))

+from heapq import heappush, heappop + -adj = [[INF] * N for _ in range(N)] +adj = [] +for _ in range(N): +    inp = tuple(map(int, input().split())) +    adj.append(tuple(zip(inp[2::2], inp[3::2]))) +checked = [False for _ in range(N)] +d = [float("inf") for _ in range(N)] +d[0] = 0 +heap = [[0, 0]]  # cost, vec +while heap: +    c, u = heappop(heap) +    if d[u] < c or checked[u]: +        continue +    for nu, nc in adj[u]: +        new_d = d[u] + nc +        if new_d < d[nu]: +            d[nu] = new_d +            heappush(heap, [d[nu], nu]) +    checked[u] = True -    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]))) +    print(("{} {}".format(n, d[n])))