#!/usr/bin/python3

n = int(eval(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]] = 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:

    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





for i, v in enumerate(d):

    print((i, v))
#!/usr/bin/python3

from heapq import heappop, heappush

n = int(eval(input()))

inf = 100 * 100000



M = [[] for i 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].append((v[j], c[j]))

result = [0] * n

S = set()

V = set(range(n))

S.add(0)

d = []

for m in M[0]:

    heappush(d, (m[1], m[0]))

T = V - S



while len(T) != 0:

    c, v = heappop(d)

    while v in S:

        c, v = heappop(d)

    result[v] = c

    S.add(v)

    T.remove(v)

    for m in M[v]:

        if m[0] in T:

            heappush(d, (result[v] + m[1], m[0]))



for i, v in enumerate(result):

    print((i, v))
#!/usr/bin/python3
n = int(eval(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]] = 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:
    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
for i, v in enumerate(d):
    print((i, v))

#!/usr/bin/python3
from heapq import heappop, heappush

n = int(eval(input()))
inf = 100 * 100000
M = [[] for i 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].append((v[j], c[j]))
result = [0] * n
S = set()
V = set(range(n))
S.add(0)
d = []
for m in M[0]:
    heappush(d, (m[1], m[0]))
T = V - S
while len(T) != 0:
    c, v = heappop(d)
    while v in S:
        c, v = heappop(d)
    result[v] = c
    S.add(v)
    T.remove(v)
    for m in M[v]:
        if m[0] in T:
            heappush(d, (result[v] + m[1], m[0]))
for i, v in enumerate(result):
    print((i, v))

+from heapq import heappop, heappush + -M = [[inf for i in range(n)] for j in range(n)] +M = [[] for i in range(n)] -        M[u][v[j]] = c[j] +        M[u].append((v[j], c[j])) +result = [0] * n -d = [inf for i in range(n)] -d[0] = 0 -count = 0 -while len(V - S) != 0: -    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 -for i, v in enumerate(d): +d = [] +for m in M[0]: +    heappush(d, (m[1], m[0])) +T = V - S +while len(T) != 0: +    c, v = heappop(d) +    while v in S: +        c, v = heappop(d) +    result[v] = c +    S.add(v) +    T.remove(v) +    for m in M[v]: +        if m[0] in T: +            heappush(d, (result[v] + m[1], m[0])) +for i, v in enumerate(result):