import scala.io.StdIn.{readInt, readLine};
import scala.collection.mutable.PriorityQueue;

object Main {
    def main(args: Array[String]): Unit = {
        val size = readInt;
        val graph: Array[List[(Int, Int)]] = new Array[List[(Int, Int)]](size); // (index, cost)
        for (i <- (0 until size)) {
            val input = readLine.split(" ").map(_.toInt).drop(2);
            val dstNum = input.length / 2;
            val dsts = (0 until dstNum).foldLeft[List[(Int,Int)]](Nil) { (dsts, j) => 
                (input(j * 2), input(j * 2 + 1)) :: dsts
            }
            graph(i) = dsts;
        }
        val output = shortestPath(size, graph).zipWithIndex.map(e => "%d %d".format(e._2, e._1));
        println(output.mkString("\n"));
    }
    
    def shortestPath(size: Int, graph: Array[List[(Int, Int)]]): Array[Int] = {
        val dist = new Array[Int](size).map(a => Int.MaxValue);
        val stat = new Array[Int](size); // 0 : 未追加, 1 : 追加済み
        implicit val ord = Ordering.by((e: (Int, Int)) => e._2).reverse;
        val pq = new PriorityQueue[(Int, Int)]();
        def go(): Unit = {
            if (!pq.isEmpty) {
                val (index, cost) = pq.dequeue;
                if (stat(index) == 0) {
                    stat(index) = 1;
                    graph(index).filter(e => stat(e._1) == 0).foreach { e =>
                        val dstIndex = e._1;
                        val newDstCost = e._2 + dist(index);
                        if (newDstCost < dist(dstIndex)) {
                            dist(dstIndex) = newDstCost;
                            pq.enqueue((dstIndex, newDstCost));
                        }
                    }
                }
                go();
            }
            
        }
        dist(0) = 0;
        pq.enqueue((0, dist(0)));
        go();
        dist;
    }
}
