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

namespace ALDS1_12_B
{   
    class Program
    {
        private static int n;
        private static int[] d;
        private static Dictionary<int, int>[] neighborList;
        private static Program.Status[] enmVisited;

        public enum Status
        {
            Yet = 0
            ,OnGoing = 1
            ,Finished = 2
        }

        static void Main(string[] args)
        {
            Program.n = int.Parse(Console.ReadLine());
            
            Program.d = new int[Program.n];
            Program.enmVisited = new Program.Status[Program.n];
            for (int i = 0; i < Program.n; i++)
            {
                Program.d[i] = (int)Math.Pow(10, 8);
                Program.enmVisited[i] = Program.Status.Yet;
            }
            Program.d[0] = 0;

            Program.neighborList = new Dictionary<int, int>[Program.n];
            for (int i = 0; i < Program.n; i++)
            {
                Program.neighborList[i] = new Dictionary<int, int>();
                int[] tmpLine = Console.ReadLine()
                                        .Split(' ')
                                        .Select(s => int.Parse(s))
                                        .ToArray();
                for (int j = 0; j < tmpLine[1]; j++)
                {
                    int vertex = tmpLine[2 * (j + 1)];
                    int distance = tmpLine[2 * (j + 1) + 1];
                    Program.neighborList[i].Add(vertex, distance);
                }
            }

            PriorityQueue priorityQueue = new PriorityQueue();
            // priorityQueue.Enqueue(0, Program.d);
            int tmpVertex = 0;

            while(Program.enmVisited.Any(i => i != Program.Status.Finished))
            {
                Program.enmVisited[tmpVertex] = Program.Status.Finished;
                foreach(KeyValuePair<int, int> pair in Program.neighborList[tmpVertex])
                {
                    if (Program.enmVisited[pair.Key] == Program.Status.Finished)
                    {
                        continue;
                    }
                    if (d[pair.Key] > d[tmpVertex] + pair.Value)
                    {
                        d[pair.Key] = d[tmpVertex] + pair.Value;
                    }
                    if (Program.enmVisited[pair.Key] == Program.Status.Yet)
                    {
                        Program.enmVisited[pair.Key] = Program.Status.OnGoing;
                        priorityQueue.Enqueue(pair.Key, Program.d);
                    }
                }
                priorityQueue.Heapfy(d);
                tmpVertex = priorityQueue.Dequeue(Program.d);
            }

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

    class PriorityQueue
    {
        int maxQueueIndex;

        int[] heap = new int[10000];
        public PriorityQueue()
        {
            this.maxQueueIndex = -1;
        }

        public int Dequeue(int[] d)
        {
            int returnIndex = -1;
            if(this.maxQueueIndex < 0)
            {
                return returnIndex;
            }

            returnIndex = this.heap[0];
            this.heap[0] = this.heap[this.maxQueueIndex];
            this.maxQueueIndex--;
            this.DownHeapfy(0, d);

            return returnIndex;
        }

        public void Enqueue(int targetVertex, int[] d)
        {
            this.maxQueueIndex++;
            this.heap[this.maxQueueIndex] = targetVertex;
            this.UpHeapfy(this.maxQueueIndex, d);
        }

        public void UpHeapfy(int targetIndex, int[] d)
        {
            if (targetIndex == 0)
            {
                return;
            }

            int parentIndex = (targetIndex + 1) / 2 - 1;
            if (d[this.heap[parentIndex]] > d[this.heap[targetIndex]])
            {
                int tmpVal = this.heap[parentIndex];
                this.heap[parentIndex] = this.heap[targetIndex];
                this.heap[targetIndex] = tmpVal;
                this.UpHeapfy(parentIndex, d);
            }
        }

        public void DownHeapfy(int targetIndex, int[] d)
        {
            if (this.maxQueueIndex < 0)
            {
                return;
            }

            int tmpIndex = targetIndex;
            int leftIndex = (targetIndex + 1) * 2 - 1;
            int rightIndex = (targetIndex + 1) * 2;
            if (leftIndex <= this.maxQueueIndex && d[this.heap[leftIndex]] < d[this.heap[tmpIndex]])
            {
                tmpIndex = leftIndex;
            }
            if (rightIndex <= this.maxQueueIndex && d[this.heap[rightIndex]] < d[this.heap[tmpIndex]])
            {
                tmpIndex = rightIndex;
            }

            if (targetIndex != tmpIndex)
            {
                int tmpVal = this.heap[targetIndex];
                this.heap[targetIndex] = this.heap[tmpIndex];
                this.heap[tmpIndex] = tmpVal;
                this.DownHeapfy(tmpIndex, d);
            }
        }
        public void Heapfy(int[] d)
        {
            for (int i = (this.maxQueueIndex + 1) / 2 - 1; i >= 0; i--)
            {
                this.DownHeapfy(i, d);
                // int tmpIndex = i;
                // int leftIndex = (tmpIndex + 1) * 2 - 1;
                // int rightIndex = (tmpIndex + 1) * 2;
                // if (leftIndex <= this.maxQueueIndex && d[this.heap[leftIndex]] < d[this.heap[tmpIndex]])
                // {
                //     tmpIndex = leftIndex;
                // }
                // if (rightIndex <= this.maxQueueIndex && d[this.heap[rightIndex]] < d[this.heap[tmpIndex]])
                // {
                //     tmpIndex = rightIndex;
                // }
                // if (tmpIndex != i)
                // {
                //     int tmpVal = this.heap[i];
                //     this.heap[i] = this.heap[tmpIndex];
                //     this.heap[tmpIndex] = tmpVal;
                // }
            }
        }
    }
}



Measured memory_bytes: 54684