For a given weighted graph $G = (V, E)$, find the shortest path from a source to each vertex. For each vertex $u$, print the total weight of edges on the shortest path from vertex $0$ to $u$.

Constraints

* $1 \leq n \leq 10,000$
* $0 \leq c_i \leq 100,000$
* $|E| < 500,000$
* All vertices are reachable from vertex $0$

Input

In the first line, an integer $n$ denoting the number of vertices in $G$ is given. In the following $n$ lines, adjacency lists for each vertex $u$ are respectively given in the following format:

$u$ $k$ $v_1$ $c_1$ $v_2$ $c_2$ ... $v_k$ $c_k$

Vertices in $G$ are named with IDs $0, 1, ..., n-1$. $u$ is ID of the target vertex and $k$ denotes its degree. $v_i (i = 1, 2, ... k)$ denote IDs of vertices adjacent to $u$ and $c_i$ denotes the weight of a directed edge connecting $u$ and $v_i$ (from $u$ to $v_i$).

Output

For each vertex, print its ID and the distance separated by a space character in a line respectively. Print in order of vertex IDs.

Example

Input

5
0 3 2 3 3 1 1 2
1 2 0 2 3 4
2 3 0 3 3 1 4 1
3 4 2 1 0 1 1 4 4 3
4 2 2 1 3 3


Output

0 0
1 2
2 2
3 1
4 3
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_C

???????§????????????????II
"""
from enum import Enum
from heapq import heappush, heappop, heapify
import itertools


class Priority_queue():
    # https://docs.python.jp/3/library/heapq.html
    def __init__(self):
        self.pq = []                         # list of entries arranged in a heap
        self.entry_finder = {}               # mapping of tasks to entries
        self.REMOVED = '<removed-task>'      # placeholder for a removed task
        self.counter = itertools.count()     # unique sequence count

    def add_task(self, task, priority=0):
        'Add a new task or update the priority of an existing task'
        if task in self.entry_finder:
            self.remove_task(task)
        count = next(self.counter)
        entry = [priority, count, task]
        self.entry_finder[task] = entry
        heappush(self.pq, entry)

    def remove_task(self, task):
        'Mark an existing task as REMOVED.  Raise KeyError if not found.'
        entry = self.entry_finder.pop(task)
        entry[-1] = self.REMOVED

    def pop_task(self):
        'Remove and return the lowest priority task. Raise KeyError if empty.'
        while self.pq:
            priority, count, task = heappop(self.pq)
            if task is not self.REMOVED:
                del self.entry_finder[task]
                return task
        raise KeyError('pop from an empty priority queue')

    def top_task(self):
        return self.pq[0][-1]

    def get_length(self):
        return len(self.pq)

    def is_empty(self):
        return self.get_length()==0


class Sssp(object):
    """ single source shortest path """
    INFINITY = 999999999
    class Status(Enum):
        """ ?????????????¨??????¶??? """
        white = 1  # ????¨????
        gray = 2  # ?¨???????
        black = 3  #?¨???????

    def __init__(self, data):
        num_of_nodes = len(data)
        self.color = [Sssp.Status.white] * num_of_nodes  # ????????????????¨??????¶???
        self.d = [Sssp.INFINITY] * num_of_nodes  # ?§???????????????????
        self.p = [-1] * num_of_nodes  # ????????????????????????????¨?????????????????????????
        self.adj = [[] for _ in range(num_of_nodes)]
        self.make_adj(data)


    def make_adj(self, data):
        # ??£??\??????????????????
        for d in data:
            my_id = d[0]
            d = d[2:]
            while len(d) > 1:
                to_node, cost = d[0], d[1]
                self.adj[my_id].insert(0, (to_node, cost))
                d = d[2:]


    def dijkstra(self, start):
        self.d[start] = 0
        pq = Priority_queue()
        pq.add_task((0, 0), 0)

        while not pq.is_empty():
            cost, u = pq.pop_task()
            self.color[u] = Sssp.Status.black
            if self.d[u] < cost:
                continue

            for v, cost in self.adj[u]:
                if self.color[v] == Sssp.Status.black:
                    continue
                if self.d[v] > self.d[u] + cost:
                    self.d[v] = self.d[u] + cost
                    pq.add_task((self.d[v], v), self.d[v])
                    self.color[v] = Sssp.Status.gray


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())
    data = []
    for i in range(num):
        data.append(list(map(int, input().split(' '))))

    # ???????????¢?´¢
    s = Sssp(data)
    s.dijkstra(0)

    # ???????????¨???
    for i in range(num):
        print('{0} {1}'.format(i, s.d[i]))