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

// 単一始点最短経路
// 与えら得た重み付きグラフについて、単一始点の最短経路のコストを求めるプログラムを作成
// 各ノードの隣接情報（id,重み）を与えられる
// ダイクストラのアルゴリズムを使用（辺に負の値が含まれるときは使えない）

public class ALDS1_12_B
{
    public struct Node
    {
        public int Id;
        public int ParentId;
        public List<int> Children;
        public List<Tuple<int, int>> Adj;
        public bool Checked;
        public int Distance;
        public Node(int id)
        {
            Id = id;
            ParentId = -2;
            Children = new List<int>();
            Adj = new List<Tuple<int, int>>();
            Checked = false;
            Distance = -1;
        }
    }

    public static void Main(string[] args)
    {
        //var exStdIn = new System.IO.StreamReader( "input.txt" );
        //System.Console.SetIn( exStdIn );

        int n = int.Parse(Console.ReadLine());

        // ノード生成
        var nodes = new Node[n];
        for (int i = 0; i < n; i++)
        {
            nodes[i] = new Node(i);
        }

        // 隣接情報の代入（id,重み）
        for (int i = 0; i < n; i++)
        {
            int[] val = Console.ReadLine().Trim().Split(' ').Select(x => int.Parse(x)).ToArray();
            int u = val[0];
            int k = val[1];
            for (int j = 0; j < k; j++)
            {
                nodes[u].Adj.Add(new Tuple<int, int>(val[2+j*2], val[2+j*2+1]));
            }
        }

        // Rootを設定
        nodes[0].ParentId = -1;
        nodes[0].Distance = 0;
        for (int i = 0; i < nodes[0].Adj.Count; i++)
        {
            nodes[nodes[0].Adj[i].Item1].Distance = nodes[0].Adj[i].Item2;
        }

        while (true)
        {
            var queue = new Queue<int>();
            // Rootをキューに追加
            queue.Enqueue(0);
            // 全て未チェック状態に変更
            for (int i = 0; i < n; i++)
            {
                nodes[i].Checked = false;
            }
            // 今回新しく追加された距離（BFSを回しつつ、木に1つずつノードを追加していく）
            int addD = Bfs(nodes, queue);
            // 距離が-1なら終了
            if (addD == -1)
            {
                break;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++)
        {
            sb.Append(i);
            sb.Append(" ");
            sb.Append(nodes[i].Distance);
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }

    public static int Bfs(Node[] nodes, Queue<int> queue)
    {
        int d = -1;
        int parent = -1;
        int target = -1;

        // Rootから辿り着けるノードの中から最小の重みで到達できるノードを探す
        while (queue.Count > 0)
        {
            var i = queue.Dequeue();
            nodes[i].Checked = true;
            for (int j = 0; j < nodes[i].Adj.Count; j++)
            {
                // 隣接ノード
                var adjId = nodes[i].Adj[j].Item1;
                var adjNode = nodes[adjId];
                var adjDistance = adjNode.Distance;
                // チェック済みならスキップ
                if (adjNode.Checked)
                {
                    continue;
                }
                if (adjNode.ParentId == -2)
                {
                    // 親が設定されてなければ、作成済みの木の隣なので距離チェックを行う
                    if (d == -1 || adjDistance < d)
                    {
                        d = adjDistance;
                        parent = i;
                        target = adjId;
                    }
                }
                else
                {
                    // 親が設定されている場合は、既に木に含まれているので、隣接行列をチェック
                    queue.Enqueue(adjId);
                }
            }
        }
        // 最小の重みで到達できるノードが見つかった場合、Rootから辿り着けるノードに追加
        if (d != -1)
        {
            nodes[target].ParentId = parent;
            nodes[parent].Children.Add(target);
            nodes[target].Distance = d;
            for (int j = 0; j < nodes[target].Adj.Count; j++)
            {
                // 隣接ノード
                var adjId = nodes[target].Adj[j].Item1;
                var adjWeight = nodes[target].Adj[j].Item2;
                var adjNode = nodes[adjId];

                if (adjNode.ParentId == -2)
                {
                    // 親が設定されておらず、rootでもないならば、距離の更新作業を行う
                    if (adjNode.Distance == -1 || nodes[target].Distance + adjWeight < adjNode.Distance)
                    {
                        nodes[adjId].Distance = nodes[target].Distance + adjWeight;
                    }
                }
            }
        }
        return d;
    }
}



Measured memory_bytes: 18724