using System;
using System.Collections.Generic;

namespace alds_12
{
	public class Program
	{
		public class pair<T, U> : IComparable where T : IComparable<T>
		{
			public pair ()
			{
			}

			public pair (T first, U second)
			{
				this.First = first;
				this.Second = second;
			}

			public int CompareTo (Object obj)
			{
				pair<T,U> cast = (pair<T,U>)obj;
				return First.CompareTo (cast.First);
			}

			public T First{ get; set; }

			public U Second { get; set; }
		}


		public class PriorityQueue<T> where T: IComparable
		{
			private T[] heap;
			private int sz = 0;
			private int count = 0;

			public PriorityQueue ()
			{
				heap = new T[50000];
			}

			private int Compare (T x, T y)
			{
				return y.CompareTo (x);
			}

			public void Push (T x)
			{
				count++;

//node number
				var i = sz++;

				while (i > 0) {
// parent node number
					var p = (i - 1) / 2;
					if (Compare (heap [p], x) <= 0)
						break;
					heap [i] = heap [p];
					i = p;
				}
				heap [i] = x;
//				Console.Write ("Push {0}", x);
			}

			public T Pop ()
			{
				count--;
				T ret = heap [0];
				T x = heap [--sz];

				int i = 0;
				while (i * 2 + 1 < sz) {
// children
					int a = i * 2 + 1;
					int b = i * 2 + 2;

					if (b < sz && Compare (heap [b], heap [a]) < 0)
						a = b;
					if (Compare (heap [a], x) >= 0)
						break;

					heap [i] = heap [a];
					i = a;
				}
				heap [i] = x;
				return ret;
			}

			public int Count ()
			{
				return count;
			}

			public bool Empty ()
			{
				return count == 0;
			}

			public T Peek ()
			{
				return heap [0];
			}

			public bool Contains (T x)
			{
				for (int i = 0; i < sz; i++) {
					if (x.Equals (heap [i]))
						return true;
				}
				return false;
			}

			public void Clear ()
			{
				while (Count () > 0)
					Pop ();
			}

			public IEnumerator<T> GetEnumerator ()
			{
				var ret = new List<T> ();
				while (this.Count () > 0) {
					ret.Add (this.Pop ());
				}

				foreach (var r in ret) {
					this.Push (r);
					yield return r;
				}
			}

			public T[] ToArray ()
			{
				T[] array = new T[sz];
				int i = 0;

				foreach (var r in this) {
					array [i++] = r;
				}

				return array;
			}
		}

		//  static private readonly int MAX = 100;
		static private readonly int INFINITY = (1 << 21);
		static private readonly int WHITE = 0;
		static private readonly int GRAY = 1;
		static private readonly int BLACK = 2;

		static private int n = -1;
		static private List<pair<int, int>>[] adj = null;
		static private PriorityQueue<pair<int, int>> pq = null;

		private static void dijkstra ()
		{
			int[] d = new int[n];
			int[] color = new int[n];
			pq = new PriorityQueue<pair<int, int>> ();

			for (int i = 0; i < n; i++) {
				d [i] = INFINITY;
				color [i] = WHITE;
			}

			d [0] = 0;
			pq.Push (new pair<int, int> (0, 0));
			color [0] = GRAY;

			while (!pq.Empty ()) {
				pair<int, int> f = pq.Peek ();
				pq.Pop ();
				int u = f.Second;
				color [u] = BLACK;

				if (d [u] < f.First * (-1)) {
					continue;
				}

				for (int i = 0; i < adj [u].Count; i++) {
					int v = adj [u] [i].First;
					if (color [v] == BLACK) {
						continue;
					}
					if (d [v] > d [u] + adj [u] [i].Second) {
						d [v] = d [u] + adj [u] [i].Second;
						pq.Push (new pair<int, int> (d [v] * (-1), v));
						color [v] = GRAY;
					}
				}
			}

			for (int i = 0; i < n; i++) {
				Console.Write ("{0} {1}\n", i, (d [i] == INFINITY ? -1 : d [i]));
			}
		}

		public static void Main ()
		{
			n = int.Parse (Console.ReadLine ());
			adj = new List<pair<int, int>>[n];

			int k, c, u, v;
			for (int i = 0; i < n; i++) {
				int s = 0;
				string[] str = Console.ReadLine ().Split (' ');
				adj [i] = new List<pair<int, int>> ();
				u = int.Parse (str [s++]);
				k = int.Parse (str [s++]);
//      Console.Write("{0}, {1}\n", u, k);
				for (int j = 0; j < k; j++) {
					v = int.Parse (str [s++]);
					c = int.Parse (str [s++]);
					adj [u].Add (new pair<int,int> (v, c));
//	Console.Write("{0}, {1}\n", v, c);
				}
			}

			dijkstra ();
		}
	}
}

Measured memory_bytes: 37876