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 override string ToString ()
			{
				return string.Format ("{0} {1}?\n", First,Second );
			}
		}


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

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

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

			public void Push (T x)
			{
				var i = size++;

				while (i > 0) {
					var p = (i - 1) / 2;
					if (Compare (heap [p], x) <= 0)
						break;
					heap [i] = heap [p];
					i = p;
				}
				heap [i] = x;
			}

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

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

					if (b < size && 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 size;
			}

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

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

		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;

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

			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) { continue; }

					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: 37828