import sys

    

global nodes

nodes = {}



def shortest_path(GRAPH):

    global nodes

    

    p1 = 0

    nodes[p1][1] = 0;



    edge={}

    total = 0

    mini = 0

    while True:

        nodes[p1][0]=True

        for p2 in range(len(nodes)):

            if nodes[p2][0]==False and (p1, p2) in GRAPH:

                tmp = nodes[p1][1] + GRAPH[(p1, p2)]

                if tmp < nodes[p2][1]:

                    nodes[p2][1] = tmp



        p1 = -1

        mini = 1000000

        for p2 in range(len(nodes)):

            if nodes[p2][0]==False and nodes[p2][1]<mini:

                p1 = p2

                mini = nodes[p2][1]

        if mini == 1000000:

            break

    return



def resultout():

    for i in range(len(nodes)):

        print("%d %d" %(i, nodes[i][1]))

    return



n = int(input())

x = {}

for i in range(n):

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

    i2 = seq.pop(0)

    n2 = seq.pop(0)

    for j in range(n2):

        j2 = seq.pop(0)

        weight = seq.pop(0)

        x[(i2, j2)] = weight

    nodes[i2] = [False, 1000000]



shortest_path(x)

resultout()
import sys

    

def shortest_path(GRAPH, distance):

    

    nodes = set()

    p1 = 0

    distance[p1] = 0



    while True:

        dp1 = distance[p1]

        gp1 = GRAPH[p1]

        status[p1]=1

        for p2 in list(gp1.keys()):

            tmp = gp1[p2] + dp1

            if status[p2]==0 and tmp < distance[p2]:

                distance[p2] = tmp

                nodes.add(p2)



        p1 = -1

        mini = 1000000

            

        for p2 in nodes:

            if distance[p2]<mini:

                p1 = p2

                mini = distance[p2]

        if mini == 1000000:

            break

        nodes.remove(p1)

    return



def resultout(distance):

    for i in range(len(distance)):

        print("%d %d" %(i, distance[i]))

    return



n = int(input())

x = [{} for i in range(n)]

status = [0 for i in range(n)]

distance = [1000000 for i in range(n)]



for i in range(n):

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

    tmp={}

    for j in range(2, len(seq), 2):

        j2, weight = seq[j:j+2]

        tmp[j2] = weight

    x[seq[0]] = tmp

    status[i] = 0



shortest_path(x, distance)

resultout(distance)
import sys

global nodes
nodes = {}


def shortest_path(GRAPH):
    global nodes
    p1 = 0
    nodes[p1][1] = 0
    edge = {}
    total = 0
    mini = 0
    while True:
        nodes[p1][0] = True
        for p2 in range(len(nodes)):
            if nodes[p2][0] == False and (p1, p2) in GRAPH:
                tmp = nodes[p1][1] + GRAPH[(p1, p2)]
                if tmp < nodes[p2][1]:
                    nodes[p2][1] = tmp
        p1 = -1
        mini = 1000000
        for p2 in range(len(nodes)):
            if nodes[p2][0] == False and nodes[p2][1] < mini:
                p1 = p2
                mini = nodes[p2][1]
        if mini == 1000000:
            break
    return


def resultout():
    for i in range(len(nodes)):
        print("%d %d" % (i, nodes[i][1]))
    return


n = int(input())
x = {}
for i in range(n):
    seq = list(map(int, input().split()))
    i2 = seq.pop(0)
    n2 = seq.pop(0)
    for j in range(n2):
        j2 = seq.pop(0)
        weight = seq.pop(0)
        x[(i2, j2)] = weight
    nodes[i2] = [False, 1000000]
shortest_path(x)
resultout()

import sys


def shortest_path(GRAPH, distance):
    nodes = set()
    p1 = 0
    distance[p1] = 0
    while True:
        dp1 = distance[p1]
        gp1 = GRAPH[p1]
        status[p1] = 1
        for p2 in list(gp1.keys()):
            tmp = gp1[p2] + dp1
            if status[p2] == 0 and tmp < distance[p2]:
                distance[p2] = tmp
                nodes.add(p2)
        p1 = -1
        mini = 1000000
        for p2 in nodes:
            if distance[p2] < mini:
                p1 = p2
                mini = distance[p2]
        if mini == 1000000:
            break
        nodes.remove(p1)
    return


def resultout(distance):
    for i in range(len(distance)):
        print("%d %d" % (i, distance[i]))
    return


n = int(input())
x = [{} for i in range(n)]
status = [0 for i in range(n)]
distance = [1000000 for i in range(n)]
for i in range(n):
    seq = list(map(int, input().split()))
    tmp = {}
    for j in range(2, len(seq), 2):
        j2, weight = seq[j : j + 2]
        tmp[j2] = weight
    x[seq[0]] = tmp
    status[i] = 0
shortest_path(x, distance)
resultout(distance)

-global nodes -nodes = {} - -def shortest_path(GRAPH): -    global nodes +def shortest_path(GRAPH, distance): +    nodes = set() -    nodes[p1][1] = 0 -    edge = {} -    total = 0 -    mini = 0 +    distance[p1] = 0 -        nodes[p1][0] = True -        for p2 in range(len(nodes)): -            if nodes[p2][0] == False and (p1, p2) in GRAPH: -                tmp = nodes[p1][1] + GRAPH[(p1, p2)] -                if tmp < nodes[p2][1]: -                    nodes[p2][1] = tmp +        dp1 = distance[p1] +        gp1 = GRAPH[p1] +        status[p1] = 1 +        for p2 in list(gp1.keys()): +            tmp = gp1[p2] + dp1 +            if status[p2] == 0 and tmp < distance[p2]: +                distance[p2] = tmp +                nodes.add(p2) -        for p2 in range(len(nodes)): -            if nodes[p2][0] == False and nodes[p2][1] < mini: +        for p2 in nodes: +            if distance[p2] < mini: -                mini = nodes[p2][1] +                mini = distance[p2] +        nodes.remove(p1) -def resultout(): -    for i in range(len(nodes)): -        print("%d %d" % (i, nodes[i][1])) +def resultout(distance): +    for i in range(len(distance)): +        print("%d %d" % (i, distance[i])) -x = {} +x = [{} for i in range(n)] +status = [0 for i in range(n)] +distance = [1000000 for i in range(n)] -    i2 = seq.pop(0) -    n2 = seq.pop(0) -    for j in range(n2): -        j2 = seq.pop(0) -        weight = seq.pop(0) -        x[(i2, j2)] = weight -    nodes[i2] = [False, 1000000] -shortest_path(x) -resultout() +    tmp = {} +    for j in range(2, len(seq), 2): +        j2, weight = seq[j : j + 2] +        tmp[j2] = weight +    x[seq[0]] = tmp +    status[i] = 0 +shortest_path(x, distance) +resultout(distance)