from heapq import*

def m():

 n=int(eval(input()))

 A=[[]for _ in[0]*n]

 for _ in[0]*n:

  e=list(map(int,input().split()))

  for i in range(e[1]):k=2*-~i;A[e[0]]+=[(e[k],e[k+1])]

 H=[[0,0]]

 d=[0]+[1e6]*n

 c=[1]*n

 while H:

  f=heappop(H)

  u=f[1]

  c[u]=0

  if d[u]>=f[0]:

   for s in A[u]:

    v=s[0]

    if c[v]and d[v]>d[u]+s[1]:

     d[v]=d[u]+s[1]

     heappush(H,[d[v],v])

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

m()

from heapq import*

I=float("inf")

def m():

 n=int(eval(input()))

 A=[[]]*n

 for _ in range(n):

  e=list(map(int,input().split()))

  A[e[0]]=list(zip(e[2::2],e[3::2]))

 d=[0]+[I]*n

 H=[(0,0)]

 while H:

  u=heappop(H)[1]

  for v,c in A[u]:

   t=d[u]+c

   if d[v]>t:

    d[v]=t

    heappush(H,(t,v))

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

m()

from heapq import *


def m():
    n = int(eval(input()))
    A = [[] for _ in [0] * n]
    for _ in [0] * n:
        e = list(map(int, input().split()))
        for i in range(e[1]):
            k = 2 * -~i
            A[e[0]] += [(e[k], e[k + 1])]
    H = [[0, 0]]
    d = [0] + [1e6] * n
    c = [1] * n
    while H:
        f = heappop(H)
        u = f[1]
        c[u] = 0
        if d[u] >= f[0]:
            for s in A[u]:
                v = s[0]
                if c[v] and d[v] > d[u] + s[1]:
                    d[v] = d[u] + s[1]
                    heappush(H, [d[v], v])
    for i in range(n):
        print((i, d[i]))


m()

from heapq import *

I = float("inf")


def m():
    n = int(eval(input()))
    A = [[]] * n
    for _ in range(n):
        e = list(map(int, input().split()))
        A[e[0]] = list(zip(e[2::2], e[3::2]))
    d = [0] + [I] * n
    H = [(0, 0)]
    while H:
        u = heappop(H)[1]
        for v, c in A[u]:
            t = d[u] + c
            if d[v] > t:
                d[v] = t
                heappush(H, (t, v))
    for i in range(n):
        print((i, d[i]))


m()

+ +I = float("inf") -    A = [[] for _ in [0] * n] -    for _ in [0] * n: +    A = [[]] * n +    for _ in range(n): -        for i in range(e[1]): -            k = 2 * -~i -            A[e[0]] += [(e[k], e[k + 1])] -    H = [[0, 0]] -    d = [0] + [1e6] * n -    c = [1] * n +        A[e[0]] = list(zip(e[2::2], e[3::2])) +    d = [0] + [I] * n +    H = [(0, 0)] -        f = heappop(H) -        u = f[1] -        c[u] = 0 -        if d[u] >= f[0]: -            for s in A[u]: -                v = s[0] -                if c[v] and d[v] > d[u] + s[1]: -                    d[v] = d[u] + s[1] -                    heappush(H, [d[v], v]) +        u = heappop(H)[1] +        for v, c in A[u]: +            t = d[u] + c +            if d[v] > t: +                d[v] = t +                heappush(H, (t, v))