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

namespace ALDS1_12_C_SingleSourceShortestPathII
{
	class Program
	{
		static void Main ( string[] args )
		{
			int vertexCount = int.Parse (Console.ReadLine ());

			Graph graph = new Graph (vertexCount, 2);

			for (int lp = 0; lp < vertexCount; lp++)
			{
				int[] inputNum = Array.ConvertAll (Console.ReadLine ().Split (' '), int.Parse);

				for (int lp2 = 0; lp2 < inputNum[1] * 2; lp2 += 2)
				{
					graph.GetPath (inputNum[0], inputNum[lp2 + 2], inputNum[lp2 + 3]);
				}
			}

			int[] result = graph.Dijkstra (0);

			//output
			int count = 0;
			Array.ForEach (result, item => Console.WriteLine (count++ + " " + item));
		}
	}

	class Graph
	{
		public Graph ( int size, int capacity = 1 )
		{
			this.Size = size;

			this.AdjacencyList = new List<Pair>[Size];
			for (int lp = 0; lp < Size; lp++)
			{
				this.AdjacencyList[lp] = new List<Pair> (capacity);
			}
		}

		private List<Pair>[] AdjacencyList { set; get; }
		private int Size { set; get; }

		public void GetPath ( int beginPoint, int adjacencyPoint, int cost )
		{
			Pair item = new Pair (adjacencyPoint, cost);
			AdjacencyList[beginPoint].Add (item);
		}

		public int[] Dijkstra ( int beginPoint )
		{
			//initialize
			const int Stay = 1;
			const int Visited = 2;
			int[] visitState = new int[Size];

			const int Infinity = int.MaxValue;
			int[] distance = Enumerable.Repeat (Infinity, Size).ToArray ();

			PriorityQueue pq = new PriorityQueue (AdjacencyList[beginPoint].Count);

			//process
			distance[beginPoint] = 0;
			pq.Insert (beginPoint, 0);

			while (!pq.IsEmpty)
			{
				//????°???????????????§??°?????§???????????????????????????
				Pair minPoint = pq.PopMinValue ();
				int minVertex = minPoint.VertexNumber;
				int minCost = minPoint.Cost;

				visitState[minVertex] = Visited;

				//????°???????????????????????????????????????????????°??????\?????§????????°
				if (minCost <= distance[minVertex])
				{
					for (int lp = 0; lp < AdjacencyList[minVertex].Count; lp++)
					{
						int vertex = AdjacencyList[minVertex][lp].VertexNumber;

						if (visitState[vertex] != Visited)
						{
							if (distance[minVertex] + AdjacencyList[minVertex][lp].Cost < distance[vertex])
							{
								distance[vertex] = distance[minVertex] + AdjacencyList[minVertex][lp].Cost;
								pq.Insert (vertex, distance[vertex]);
								visitState[vertex] = Stay;
							}
						}
					}
				}
			}
		
			return distance;
		}
	}

	public class Pair : IComparable<Pair>
	{
		public Pair ( int number, int cost )
		{
			this.VertexNumber = number;
			this.Cost = cost;
		}

		public int VertexNumber { private set; get; }
		public int Cost { private set; get; }

		public int CompareTo ( Pair ob )
		{
			if (this.Cost < ob.Cost)
			{
				return -1;
			}
			else if (this.Cost == ob.Cost)
			{
				return 0;
			}
			else
			{
				return 1;
			}
		}
	}

	class PriorityQueue
	{
		public PriorityQueue ( int capacity = 5 )
		{
			this.Heap = new List<Pair> (capacity);
			this.Heap.Add (null);	//padding
			this.HeapIndex = 0;
		}

		private List<Pair> Heap { set; get; }
		private int HeapIndex { set; get; }
		public bool IsEmpty { get { return HeapIndex == 0; } }

		private int ParentKey ( int index )
		{
			return index / 2;
		}
		private int LeftKey ( int index )
		{
			return index * 2;
		}
		private int RightKey ( int index )
		{
			return index * 2 + 1;
		}

		public void Insert ( int vertexNumver, int cost )
		{
			Pair p = new Pair (vertexNumver, cost);

			HeapIndex++;

			if (HeapIndex < Heap.Count)
			{
				Heap[HeapIndex] = p;
			}
			else
			{
				Heap.Add (p);
			}

			HeapIncreaseKey (p);
		}

		public Pair PopMinValue ()
		{
			if (HeapIndex < 1)
			{
				Console.WriteLine ("Pop Error");
			}

			Pair min = Heap[1];
			Heap[1] = Heap[HeapIndex];
			HeapIndex--;

			MinHeapify (1);

			return min;
		}

		private void HeapIncreaseKey ( Pair item )
		{
			int childIndex = HeapIndex;
			int parentKey = ParentKey (childIndex);

			while (1 < childIndex && Heap[childIndex].CompareTo (Heap[parentKey]) < 0)
			{
				var tmp = Heap[childIndex];
				Heap[childIndex] = Heap[parentKey];
				Heap[parentKey] = tmp;

				childIndex = ParentKey (childIndex);
				parentKey = ParentKey (childIndex);
			}
		}

		private void MinHeapify ( int index )
		{
			int leftKey = LeftKey (index);
			int rightKey = RightKey (index);

			int smallest;

			if (leftKey <= HeapIndex && Heap[leftKey].CompareTo (Heap[index]) < 0)
			{
				smallest = leftKey;
			}
			else
			{
				smallest = index;
			}
			if (rightKey <= HeapIndex && Heap[rightKey].CompareTo (Heap[smallest]) < 0)
			{
				smallest = rightKey;
			}

			if (smallest != index)
			{
				var tmp = Heap[index];
				Heap[index] = Heap[smallest];
				Heap[smallest] = tmp;

				MinHeapify (smallest);
			}
		}
	}
}

Measured memory_bytes: 37112