using System;
using System.Collections.Generic;


public class PriorityQueue<T> where T: IComparable
{
	private IComparer<T> _comparer = null;
	private int _type = 0;

	private T[] _heap;
	private int _sz = 0;

	private int _count = 0;

	/// <summary>
	/// Priority Queue with custom comparer
	/// </summary>
	public PriorityQueue(int maxSize, IComparer<T> comparer)
	{
		_heap = new T[maxSize];
		_comparer = comparer;
	}

	/// <summary>
	/// Priority queue
	/// </summary>
	/// <param name="maxSize">max size</param>
	/// <param name="type">0: asc, 1:desc</param>
	public PriorityQueue(int maxSize, int type = 0)
	{
		_heap = new T[maxSize];
		_type = type;
	}

	private int Compare(T x, T y)
	{
		if (_comparer != null) return _comparer.Compare(x, y);
		return _type == 0 ? x.CompareTo(y) : 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;
	}

	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 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 (this.Count() > 0) this.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;
	}
};


public class Program
{

	const int MAX = 10000;
	const int INFINITY = (1 << 20);
	const int WHITE = 0;
	const int GRAY = 1;
	const int BLACK = 2;

	static List <Tuple <int, int>>[] adj;

	public static void Main() {
		// ??°???????????????
		int n = int.Parse(Console.ReadLine());
		adj = new List<Tuple<int, int>>[n];
		for (int i = 0; i < n; ++i) {
			adj [i] = new List<Tuple<int,int>> ();
		}

		// ?????????????????????
		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]);

				adj [u].Add (new Tuple<int,int> (v, c));

			}

		}


		// ??????????????¢?´¢
		dijkstra (n);
	}


	//
	// dijkstra - ????????????????????????????????????????????¢?´¢
	//
	//
	static void dijkstra (int n) {

		PriorityQueue <Tuple<int, int>> PQ = new PriorityQueue<Tuple<int,int>> (n, 1);
		int[] color = new int[MAX];
		int[] d = new int[MAX];

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

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

		while (PQ.Count() > 0) {
			Tuple<int, int> f = PQ.Pop ();
			int u = f.Item2;
			color [u] = BLACK;

			if (d [u] < f.Item1 * (-1))
				continue;

			for (int j = 0; j < adj [u].Count; j++) {
				int v = adj [u] [j].Item1;
				if (color [v] == BLACK)
					continue;
				if (d [v] > d [u] + adj [u][j].Item2) {
					d [v] = d [u] + adj [u][j].Item2;

					PQ.Push (new Tuple<int,int> (d[v] * (-1), v));

					color [v] = GRAY;
				}
			}
		}

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

	}

}