import scala.annotation.tailrec;
import scala.io.StdIn.{readInt, readLine};
object Main {
    def main(args: Array[String]): Unit = {
        val size = readInt;
        val g = new Graph(size);
        (0 until size).foreach { i => 
            readLine.trim.split(" ").map(_.toInt).toList match {
                case parent :: childs :: xs => {
                    (0 until childs).foldLeft(xs) { (list, i) => 
                        list match {
                            case child :: weight :: xxs =>
                                g.add(parent, child, weight);
                                xxs;
                            case _ => 
                                list;
                        }
                    }
                }
                case _ => ();
            }
        }
        g.dijkstra(0)._2.zipWithIndex.foreach { e => println("%d %d".format(e._2, e._1))}
    }
}
case class Graph(size: Int) {
    class COLOR;
    case object WHITE extends COLOR;
    case object GRAY extends COLOR;
    case object BLACK extends COLOR;
    val matrix = Array.ofDim[Int](5,5).map( y => y.map(x => -1));
    def add(node: Int, child: Int, weight: Int): Unit = matrix(node)(child) = weight;
    def dijkstra(start: Int): (Array[Int], Array[Int]) = {
        val colors: Array[COLOR] = new Array[COLOR](size).map(e => WHITE);
        val distances = new Array[Int](size).map( e => Int.MaxValue);
        val parents = new Array[Int](size);
        @tailrec
        def _dijkstra(curr: Int): Unit = {
            // 追加済みノード郡の隣接ノードから距離が最小となるノードの index を取得する。
            val minIdx = (0 until size).filter( i => colors(i) != BLACK).foldLeft(-1) { (idx, i) =>
                // curr の隣接ノードの場合
                if (matrix(curr)(i) != -1) {
                    colors(i) = GRAY;
                    // 新しく計算した距離の方が既存の距離よりも小さい場合、親ノードと距離を更新する
                    val newWeight = matrix(curr)(i) + distances(curr);
                    if (newWeight < distances(i)) {
                        distances(i) = newWeight;
                        parents(i) = curr;
                    }
                }
                colors(i) match {
                    case WHITE => idx;
                    case GRAY => if (idx == -1 || distances(i) < distances(idx)) i else idx;
                }
            }
            // 追加済みノード郡から遷移可能なノードがなくなったら処理終了。
            if (minIdx != -1) {
                colors(minIdx) = BLACK;
                _dijkstra(minIdx);
            }
        }
        
        distances(start) = 0;
        parents(start) = -1;
        colors(start) = BLACK;
        _dijkstra(start);
        (parents, distances);
    }
}

