using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _20190129_AOJ
{
    class ALDS1_12B
    {
        static void Main(string[] args)
        {
            for (;;)
            {
                string line = Console.ReadLine();
                if (string.IsNullOrEmpty(line))
                {
                    break;
                }

                int n = int.Parse(line);
                int[,] map = CreateMap(n);
                for (int i = 0; i < n; i++)
                {
                    int[] iarr = ReadIntArr();
                    for (int j = 2; j < iarr.Length; j += 2)
                    {
                        map[i, iarr[j]] = iarr[j + 1];
                    }
                }

                int[] d = new int[n];
                for(int i=1;i<n;i++)
                {
                    d[i] = int.MaxValue;
                }
                int[] prev = Enumerable.Repeat<int>(-1, n).ToArray();

                HashSet<int> Q = new HashSet<int>();
                for (int i = 0; i < n; i++)
                {
                    Q.Add(i);
                }

                while (Q.Count > 0)
                {
                    int u = PopMin(Q, d);
                    for (int v = 0; v < n; v++)
                    {
                        int len = map[u, v];
                        if (len >= 0)
                        {
                            if (d[v] > d[u] + len)
                            {
                                d[v] = d[u] + len;
                                prev[v] = u;
                            }
                        }
                    }
                }

                for (int i = 0; i < n; i++)
                {
                    Console.WriteLine("{0} {1}", i, d[i]);
                }
            }
        }

        static int GetMinIndex(int[] arr)
        {
            int idx = 0;
            int min = arr[0];
            for(int i=1;i<arr.Length;i++)
            {
                if (min > arr[i])
                {
                    min = arr[i];
                    idx = i;
                }
            }

            return idx;
        }

        static int PopMin(HashSet<int> q, int[] d)
        {
            int min = int.MaxValue;
            int rv = -1;
            foreach (var v in q)
            {
                if (min > d[v])
                {
                    min = d[v];
                    rv = v;
                }
            }

            q.Remove(rv);

            return rv;
        }

        static int[,] CreateMap(int n)
        {
            int[,] map = new int[n, n];
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    map[i, j] = -1;
                }
            }
            return map;
        }

        static int ReadInt() { return int.Parse(Console.ReadLine()); }
        static double ReadDouble() { return double.Parse(Console.ReadLine()); }
        static int[] ReadIntArr(char dlm = ' ') { return Console.ReadLine().Split(dlm).Select(x => int.Parse(x)).ToArray(); }
        static double[] ReadDoubleArr(char dlm = ' ') { return Console.ReadLine().Split(dlm).Select(x => double.Parse(x)).ToArray(); }
        static string[] ReadStringArr(char dlm = ' ') { return Console.ReadLine().Split(dlm).ToArray(); }
    }
}



Measured memory_bytes: 16656