using System;
using System.Collections.Generic;
using System.Text;
                     
public class Program
{
    static int[] minCost;
     
    public static void Main()
    {
        int n = int.Parse(Console.ReadLine());
         
        Node[] G = new Node[n];
        minCost = new int[n];
         
        for(int i = 0; i < n; i++) {
            G[i] = new Node(i);
            minCost[i] = -1;
 
            var cells = Array.ConvertAll(Console.ReadLine().Split(" ".ToCharArray()), int.Parse);
             
            for(int j = 0; j < cells[1]; j++) {
                G[i].E.Add(new Edge(cells[2*j+2], cells[2*j+3]));
            }
        }
         
        PriorityQueue<Edge> PQ = new PriorityQueue<Edge>(10000, (a,b) => a.Cost - b.Cost);
         
        PQ.Enqueue(new Edge(0,0));
         
        while(PQ.Any()) {
            Edge e = PQ.Dequeue();
            if(minCost[e.Next] > e.Cost || minCost[e.Next] == -1) { 
                minCost[e.Next] = e.Cost;
             
                for(int i = 0; i < G[e.Next].E.Count; i++) {
                    G[e.Next].E[i].Cost += e.Cost;
                    if(minCost[G[e.Next].E[i].Next] == -1) PQ.Enqueue(G[e.Next].E[i]);
                }
            }
        }
         
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i<n; i++) {
            sb.Append(i);
            sb.Append(" ");
            sb.Append(minCost[i]);
            sb.AppendLine();
        }
        Console.Write(sb);
    }
}
 
class Edge
{
    public int Next { private set; get; }
    public int Cost { set; get; }
     
    public Edge(int n, int c)
    {
        this.Next = n;
        this.Cost = c;
    }
}
 
class Node
{
    public int Id { private set; get; }
    public List<Edge> E;
     
    public Node (int v)
    {
        this.Id = v;
        E = new List<Edge>();
    }
}
 
class PriorityQueue<T>
{
    private readonly List<T> heap;
    private readonly Comparison<T> compare;
    private int size;
    public PriorityQueue() : this(Comparer<T>.Default) {} 
    public PriorityQueue(IComparer<T> comparer) : this(16, comparer.Compare) { }
    public PriorityQueue(Comparison<T> comparison) : this(16, comparison) { }
    public PriorityQueue(int capacity, Comparison<T> comparison)
    {
        this.heap = new List<T>(capacity);
        this.compare = comparison;
    }
    public void Enqueue(T item)
    {
        this.heap.Add(item);
        var i = size++;
        while (i > 0)
        {
            var p = (i - 1) >> 1;
            if (compare(this.heap[p], item) <= 0)
                break;
            this.heap[i] = heap[p];
            i = p;
        }
        this.heap[i] = item;
 
    }
    public T Dequeue()
    {
        var ret = this.heap[0];
        var x = this.heap[--size];
        var i = 0;
        while ((i << 1) + 1 < size)
        {
            var a = (i << 1) + 1;
            var b = (i << 1) + 2;
            if (b < size && compare(heap[b], heap[a]) < 0) a = b;
            if (compare(heap[a], x) >= 0)
                break;
            heap[i] = heap[a];
            i = a;
        }
        heap[i] = x;
        heap.RemoveAt(size);
        return ret;
    }
    public T Peek() { return heap[0]; }
    public int Count { get { return size; } }
    public bool Any() { return size > 0; }
}

Measured memory_bytes: 43068