using System;
using System.Collections.Generic;

namespace Dijkstra
{
	class MainClass
	{

		enum NODE_STATE {
			YET = 0,
			NOW,
			DONE
		};

		//
		// ??°??????????????????
		//
		public class Node
		{
			public const int INFINITY = (1 << 20);


			// ??????????????????ID
			public int nodeId;
			// ?§??????????????????¢
			public int distFromStart;
			// ??????????????¢?´¢??¶???
			public int state;
			// ??£??\??????????????????ID
			public Dictionary <int, int> adjacents;
			// ?§??????????????????¢


			public Node (int nid)
			{
				nodeId = nid;
				adjacents = new Dictionary<int, int> ();
			}

			// ?§??????????????????¢?????????????¨????
			public void setDistFromStartAsInf() {
				distFromStart = INFINITY;
			}

			// ??¢?´¢??¶???????????????
			public void setSearchStateYet() {
				state = (int)NODE_STATE.YET;
			}

			//
			// ??£??\??????????????????
			//
			// @param (nid)		????????????????????????ID
			// @param (cost)	????????????????????????????????????
			public void AddAdjacent(int nid, int cost) {
				adjacents.Add (nid, cost);
			}

			//
			// ??????
			//
			public void dumpNode() {
				foreach (var key in adjacents.Keys) {
					Console.WriteLine (string.Format ("{0} => {1} : {2}", nodeId, key, adjacents[key]));
				}
			}

		}

		//
		// ??°???????????????????£??????£??\??¢???
		//
		public class AdjacentTree
		{
			private List <Node> _tree;

			public AdjacentTree(int numNodes)
			{
				_tree = new List<Node> (numNodes);
				for (int i = 0; i < numNodes; ++i) {
					_tree.Add(new Node(i));
				}
			}

			//
			// ??????????????°?????????
			//
			public void AddNodes(int nidFrom, int nidTo, int cost) {
				_tree [nidFrom].AddAdjacent (nidTo, cost);
			}

			//
			// ??????????????¢?´¢???????????????????????????
			//
			public void DijkstraSearch1(int startNodeId) {

				// ??¨?????????????§??????????????????¢???????????§???
				foreach (Node node in _tree) {
					node.setDistFromStartAsInf ();
					node.setSearchStateYet ();
				}

				// ?§????????¨????
				Node curNode = _tree[startNodeId];
				curNode.distFromStart = 0;
				curNode.state = (int)NODE_STATE.NOW;

				while (true) {

					// ??£??\?????????????????????????????????????°???????????????????
					int minNid = -1;
					int minCost = Int32.MaxValue;
					for (int i = 0; i < _tree.Count; ++i) {
						if (minCost > _tree [i].distFromStart && 
							_tree [i].state != (int)NODE_STATE.DONE) {
							minNid = i;
							minCost = _tree [i].distFromStart;
						}
					}
						
					if (minNid == -1)
						break;

					// ?????????????°??????????????????£??\???????????????????????????????¨????
					Node minNode = _tree [minNid];
					minNode.distFromStart = minCost;
					minNode.state = (int)NODE_STATE.DONE;
					foreach (int adjNid in minNode.adjacents.Keys) {
						Node adjNode = _tree [adjNid];
						if (adjNode.state != (int)NODE_STATE.DONE &&
							(minNode.distFromStart + minNode.adjacents[adjNid]) < adjNode.distFromStart) {

							adjNode.distFromStart = minNode.distFromStart + minNode.adjacents [adjNid];
							adjNode.state = (int)NODE_STATE.NOW;

						}
					}

				}

				foreach (Node node in _tree) {
					Console.WriteLine (string.Format ("{0} {1}", node.nodeId, node.distFromStart));
				}

			}

			//
			// ??????
			//
			public void dumpTree() {
				foreach (Node node in _tree) {
					node.dumpNode ();
				}
			}

		}

		public static void Main (string[] args)
		{

			// ??°???????????????
			int n = int.Parse(Console.ReadLine());
			AdjacentTree adjTree = new AdjacentTree (n);

			// ?????????????????????
			string readLine = null;
			for (int i = 0; i < n; ++i) {
				
				readLine = Console.ReadLine ();
				string[] splitedNums = readLine.Split (' ');
				//int u = int.Parse (splitedNums [0]);
				int k = int.Parse (splitedNums[1]);

				// ??£??\????????¨?????????????????????
				for (int j = 0; j < k; ++j) {
					int v = int.Parse (splitedNums[2 + j * 2]);
					int c = int.Parse (splitedNums[2 + j * 2 + 1]);
					adjTree.AddNodes (i, v, c);
				}
			}

			// ??????????????¢?´¢
			adjTree.DijkstraSearch1(0);

		}
	}
}

Measured memory_bytes: 46876