from collections import deque

INF = float("inf")

def MAIN():

    n = int(eval(input()))

    G = [[i, INF] for i in range(n)]

    G[0][1] = 0

    m = {}

    for _ in range(n):

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

        m[A[0]] = {}

        for i in range(2, len(A), 2):

            m[A[0]][A[i]] = A[i + 1]

    dp = deque([0])

    while dp:

        u = dp.popleft()

        for v, c in list(m[u].items()):

            if G[v][1] > G[u][1] + c:

                G[v][1] = G[u][1] + c

                dp.append(v)

    print(("\n".join(" ".join(map(str, a)) for a in G)))

MAIN()



from heapq import heapify, heappush, heappop

INF = float("inf")

def MAIN():

    n = int(eval(input()))

    G = [[i, INF] for i in range(n)]

    G[0][1] = 0

    m = {}

    for _ in range(n):

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

        m[A[0]] = {}

        for i in range(2, len(A), 2):

            m[A[0]][A[i]] = A[i + 1]

    dp = [(0, 0)]

    while dp:

        cost, u = heappop(dp)

        for v, c in list(m[u].items()):

            if G[v][1] > G[u][1] + c:

                G[v][1] = G[u][1] + c

                heappush(dp, (G[v][1], v))

    print(("\n".join(" ".join(map(str, a)) for a in G)))

MAIN()



from collections import deque

INF = float("inf")


def MAIN():
    n = int(eval(input()))
    G = [[i, INF] for i in range(n)]
    G[0][1] = 0
    m = {}
    for _ in range(n):
        A = list(map(int, input().split()))
        m[A[0]] = {}
        for i in range(2, len(A), 2):
            m[A[0]][A[i]] = A[i + 1]
    dp = deque([0])
    while dp:
        u = dp.popleft()
        for v, c in list(m[u].items()):
            if G[v][1] > G[u][1] + c:
                G[v][1] = G[u][1] + c
                dp.append(v)
    print(("\n".join(" ".join(map(str, a)) for a in G)))


MAIN()

from heapq import heapify, heappush, heappop

INF = float("inf")


def MAIN():
    n = int(eval(input()))
    G = [[i, INF] for i in range(n)]
    G[0][1] = 0
    m = {}
    for _ in range(n):
        A = list(map(int, input().split()))
        m[A[0]] = {}
        for i in range(2, len(A), 2):
            m[A[0]][A[i]] = A[i + 1]
    dp = [(0, 0)]
    while dp:
        cost, u = heappop(dp)
        for v, c in list(m[u].items()):
            if G[v][1] > G[u][1] + c:
                G[v][1] = G[u][1] + c
                heappush(dp, (G[v][1], v))
    print(("\n".join(" ".join(map(str, a)) for a in G)))


MAIN()

-from collections import deque +from heapq import heapify, heappush, heappop -    dp = deque([0]) +    dp = [(0, 0)] -        u = dp.popleft() +        cost, u = heappop(dp) -                dp.append(v) +                heappush(dp, (G[v][1], v))