#coding:utf-8

inf = 1000000

n = int(eval(input()))

M = [[inf for i in range(n)] for j in range(n)]

vwMtrx = []

for i in range(n):

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

    u = data[0]

    k = data[1]

    col = []

    for j in range(0,2*k,2):

        v, w = data[j+2], data[j+3]

        M[u][v] = w

        col.append([v,w])

    vwMtrx.append(col)



def dijkstra(s):

    color = ["white" for i in range(n)]

    d = [inf for i in range(n)]

    p = [-1 for i in range(n)]

    d[s] = 0

    Q = [[s,0]]

    while Q != []:

        u = min(Q, key=lambda x:x[1])

        Q = [List for List in Q if List != u]

        u = u[0]

        color[u] = "black"



        vwList = vwMtrx[u]

        

        for vw in vwList:

            v,w = vw[0],vw[1]

            if color[v] != "black" and M[u][v] != inf:

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

                    d[v] = d[u] + M[u][v]

                    p[v] = u

                    color[v] = "gray"

                    Q.append([v, d[v]])



    return d



dList = dijkstra(0)

for i, d in enumerate(dList):

    print((i,d))



#coding: utf-8



inf = 1000000000





def dijkstra(s):

    d = [inf for i in range(n)]

    color = ["white" for i in range(n)]

    p = [-1 for i in range(n)]

    d[s] = 0



    while True:

        mincost = inf

        for i in range(n):

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

                mincost = d[i]

                u = i

        if mincost == inf:

            break



        color[u] = "black"



        for v in range(n):

            if color[v] != "black" and mtrx[u][v] != False:

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

                    d[v] = d[u] + mtrx[u][v]

                    p[v] = u

                    color[v] = "gray"

    return d



n = int(eval(input()))

mtrx = [[False for j in range(n)] for i in range(n)]

for i in range(n):

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

    k = data[1]

    for num in range(k):

        mtrx[i][data[2+2*num]] = data[2+2*num+1]



d = dijkstra(0)



for i, num in enumerate(d):

    print((i,num))



# coding:utf-8
inf = 1000000
n = int(eval(input()))
M = [[inf for i in range(n)] for j in range(n)]
vwMtrx = []
for i in range(n):
    data = list(map(int, input().split()))
    u = data[0]
    k = data[1]
    col = []
    for j in range(0, 2 * k, 2):
        v, w = data[j + 2], data[j + 3]
        M[u][v] = w
        col.append([v, w])
    vwMtrx.append(col)


def dijkstra(s):
    color = ["white" for i in range(n)]
    d = [inf for i in range(n)]
    p = [-1 for i in range(n)]
    d[s] = 0
    Q = [[s, 0]]
    while Q != []:
        u = min(Q, key=lambda x: x[1])
        Q = [List for List in Q if List != u]
        u = u[0]
        color[u] = "black"
        vwList = vwMtrx[u]
        for vw in vwList:
            v, w = vw[0], vw[1]
            if color[v] != "black" and M[u][v] != inf:
                if d[u] + M[u][v] < d[v]:
                    d[v] = d[u] + M[u][v]
                    p[v] = u
                    color[v] = "gray"
                    Q.append([v, d[v]])
    return d


dList = dijkstra(0)
for i, d in enumerate(dList):
    print((i, d))

# coding: utf-8
inf = 1000000000


def dijkstra(s):
    d = [inf for i in range(n)]
    color = ["white" for i in range(n)]
    p = [-1 for i in range(n)]
    d[s] = 0
    while True:
        mincost = inf
        for i in range(n):
            if color[i] != "black" and d[i] < mincost:
                mincost = d[i]
                u = i
        if mincost == inf:
            break
        color[u] = "black"
        for v in range(n):
            if color[v] != "black" and mtrx[u][v] != False:
                if d[u] + mtrx[u][v] < d[v]:
                    d[v] = d[u] + mtrx[u][v]
                    p[v] = u
                    color[v] = "gray"
    return d


n = int(eval(input()))
mtrx = [[False for j in range(n)] for i in range(n)]
for i in range(n):
    data = list(map(int, input().split()))
    k = data[1]
    for num in range(k):
        mtrx[i][data[2 + 2 * num]] = data[2 + 2 * num + 1]
d = dijkstra(0)
for i, num in enumerate(d):
    print((i, num))

-# coding:utf-8 -inf = 1000000 -n = int(eval(input())) -M = [[inf for i in range(n)] for j in range(n)] -vwMtrx = [] -for i in range(n): -    data = list(map(int, input().split())) -    u = data[0] -    k = data[1] -    col = [] -    for j in range(0, 2 * k, 2): -        v, w = data[j + 2], data[j + 3] -        M[u][v] = w -        col.append([v, w]) -    vwMtrx.append(col) +# coding: utf-8 +inf = 1000000000 +    d = [inf for i in range(n)] -    d = [inf for i in range(n)] -    Q = [[s, 0]] -    while Q != []: -        u = min(Q, key=lambda x: x[1]) -        Q = [List for List in Q if List != u] -        u = u[0] +    while True: +        mincost = inf +        for i in range(n): +            if color[i] != "black" and d[i] < mincost: +                mincost = d[i] +                u = i +        if mincost == inf: +            break -        vwList = vwMtrx[u] -        for vw in vwList: -            v, w = vw[0], vw[1] -            if color[v] != "black" and M[u][v] != inf: -                if d[u] + M[u][v] < d[v]: -                    d[v] = d[u] + M[u][v] +        for v in range(n): +            if color[v] != "black" and mtrx[u][v] != False: +                if d[u] + mtrx[u][v] < d[v]: +                    d[v] = d[u] + mtrx[u][v] -                    Q.append([v, d[v]]) -dList = dijkstra(0) -for i, d in enumerate(dList): -    print((i, d)) +n = int(eval(input())) +mtrx = [[False for j in range(n)] for i in range(n)] +for i in range(n): +    data = list(map(int, input().split())) +    k = data[1] +    for num in range(k): +        mtrx[i][data[2 + 2 * num]] = data[2 + 2 * num + 1] +d = dijkstra(0) +for i, num in enumerate(d): +    print((i, num))