def dijkstra(s):

    global d

    color=[0]*n

    d=[float('inf')]*n

    d[s]=0

    while True:

        mincost=float('inf')

        for i in range(n):

            if color[i]!=2 and d[i]<mincost:

                mincost=d[i]

                u=i

        if mincost==float('inf'):

            break

        color[u]=2

        for v in range(n):

            if color[v]!=2 and m[u][v]!=0:

                if d[u]+m[u][v]<d[v]:

                    d[v]=d[u]+m[u][v]

                    color[v]=1



if __name__=='__main__':

    n=eval(input())

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

    for i in range(n):

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

        for j in range(2*en[1]):

            if j%2==0:

                enid=en[2+j]

            else:

                m[en[0]][enid]=en[2+j]

    dijkstra(0)

    for i in range(n):

        print(i,d[i])
import heapq



def dijkstra(s,g,c):

    d=[float('inf')]*n

    d[s]=0

    heapq.heappush(pq,[0,s])

    while len(pq)!=0:

        t,u=heapq.heappop(pq)

        if d[u]<t:

            continue

        for v in g[u]:

            if d[u]+c[u][v]<d[v]:

                d[v]=d[u]+c[u][v]

                heapq.heappush(pq,[d[v],v])

    return d



n=int(input())

g=[[] for _ in range(n)]

cost=[[10**9+5]*n for i in range(n)]



for i in range(n):

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

    u=en[0];k=en[1];v=en[2:-1:2];c=en[3::2]

    for j in range(k):

        g[u].append(v[j])

        cost[u][v[j]]=c[j]



pq=[]

dist=dijkstra(0,g,cost)



for i in range(n):

    print(i,dist[i])
def dijkstra(s):
    global d
    color = [0] * n
    d = [float("inf")] * n
    d[s] = 0
    while True:
        mincost = float("inf")
        for i in range(n):
            if color[i] != 2 and d[i] < mincost:
                mincost = d[i]
                u = i
        if mincost == float("inf"):
            break
        color[u] = 2
        for v in range(n):
            if color[v] != 2 and m[u][v] != 0:
                if d[u] + m[u][v] < d[v]:
                    d[v] = d[u] + m[u][v]
                    color[v] = 1


if __name__ == "__main__":
    n = eval(input())
    m = [[0] * n for i in range(n)]
    for i in range(n):
        en = list(map(int, input().split()))
        for j in range(2 * en[1]):
            if j % 2 == 0:
                enid = en[2 + j]
            else:
                m[en[0]][enid] = en[2 + j]
    dijkstra(0)
    for i in range(n):
        print(i, d[i])

import heapq


def dijkstra(s, g, c):
    d = [float("inf")] * n
    d[s] = 0
    heapq.heappush(pq, [0, s])
    while len(pq) != 0:
        t, u = heapq.heappop(pq)
        if d[u] < t:
            continue
        for v in g[u]:
            if d[u] + c[u][v] < d[v]:
                d[v] = d[u] + c[u][v]
                heapq.heappush(pq, [d[v], v])
    return d


n = int(input())
g = [[] for _ in range(n)]
cost = [[10**9 + 5] * n for i in range(n)]
for i in range(n):
    en = list(map(int, input().split()))
    u = en[0]
    k = en[1]
    v = en[2:-1:2]
    c = en[3::2]
    for j in range(k):
        g[u].append(v[j])
        cost[u][v[j]] = c[j]
pq = []
dist = dijkstra(0, g, cost)
for i in range(n):
    print(i, dist[i])

-def dijkstra(s): -    global d -    color = [0] * n +import heapq + + +def dijkstra(s, g, c): -    while True: -        mincost = float("inf") -        for i in range(n): -            if color[i] != 2 and d[i] < mincost: -                mincost = d[i] -                u = i -        if mincost == float("inf"): -            break -        color[u] = 2 -        for v in range(n): -            if color[v] != 2 and m[u][v] != 0: -                if d[u] + m[u][v] < d[v]: -                    d[v] = d[u] + m[u][v] -                    color[v] = 1 +    heapq.heappush(pq, [0, s]) +    while len(pq) != 0: +        t, u = heapq.heappop(pq) +        if d[u] < t: +            continue +        for v in g[u]: +            if d[u] + c[u][v] < d[v]: +                d[v] = d[u] + c[u][v] +                heapq.heappush(pq, [d[v], v]) +    return d -if __name__ == "__main__": -    n = eval(input()) -    m = [[0] * n for i in range(n)] -    for i in range(n): -        en = list(map(int, input().split())) -        for j in range(2 * en[1]): -            if j % 2 == 0: -                enid = en[2 + j] -            else: -                m[en[0]][enid] = en[2 + j] -    dijkstra(0) -    for i in range(n): -        print(i, d[i]) +n = int(input()) +g = [[] for _ in range(n)] +cost = [[10**9 + 5] * n for i in range(n)] +for i in range(n): +    en = list(map(int, input().split())) +    u = en[0] +    k = en[1] +    v = en[2:-1:2] +    c = en[3::2] +    for j in range(k): +        g[u].append(v[j]) +        cost[u][v[j]] = c[j] +pq = [] +dist = dijkstra(0, g, cost) +for i in range(n): +    print(i, dist[i])