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

object Main {
    def main(args: Array[String]): Unit = {
        val n = readInt;
        val ig = new IntGraph(n);
        for (i <- (0 until n)) {
            val line = readLine.split(" ").map(_.toInt);
            val src = line(0);
            val dstNum = line(1);
            for (j <- (0 until dstNum)) {
                val dst = 2 + (2 * j);
                val cost = 2 + (2 * j) + 1;
                ig.add(src, line(dst), line(cost));
            }
        }
        ig.shortestPath(0).zipWithIndex.foreach { e => println("%d %d".format(e._2, e._1))};
    }
}

class IntGraph(size: Int) {
    val m: Array[List[(Int, Int)]] = new Array[List[(Int, Int)]](size).map(e => Nil);
    def add(src: Int, dst: Int, cost: Int): Unit = m(src) = (dst, cost) :: m(src);
    def shortestPath(start: Int): Array[Int] = {
        val stat = new Array[Int](size); // 0: 未追加, 1: 追加済み
        val dist = new Array[Int](size).map( e => Int.MaxValue);
        val pq = new PriorityQueue[(Int, Int)]()(Ordering.by((e: (Int, Int)) => e._2).reverse);
        var cnt = 0;
        
        dist(start) = 0;
        pq.enqueue((start, dist(start)));
        while (cnt < size && pq.isEmpty == false) {
            val (src, srcCost) = pq.dequeue;
            if (stat(src) != 1) {
                stat(src) = 1;
                cnt += 1;
                for ((dstIdx, dstCost) <- m(src)) {
                    val newCost = dstCost + srcCost;
                    if (stat(dstIdx) != 1 && newCost < dist(dstIdx)) {
                        dist(dstIdx) = newCost;
                        pq.enqueue((dstIdx, newCost));
                    }
                }
            }
        }
        dist;
    }
}
