import scala.collection.mutable.ArraySeq;
import scala.annotation.tailrec;
import scala.io.StdIn.{readInt, readLine};
object Main {
    def main(args: Array[String]): Unit = {
        val n = readInt;
        val ig = new IntGraph(n);
        (0 until n).foreach { i => 
            readLine.split(" ").map(_.toInt).toList match {
                case parent :: dstNum :: dst => {
                    (0 until dstNum).foldLeft(dst) { (restDst, i) =>
                        restDst match {
                            case child :: weight :: xs => ig.add(parent, child, weight); xs;
                            case _ => restDst;
                        }
                    }
                }
                case _ => ();
            }
        }
        ig.shortestPath(0)._1.zipWithIndex.foreach { e => println("%d %d".format(e._2, e._1))};
    }
}

case class IntGraph(n: Int) {
    case class Node(idx: Int, weight: Int);
    sealed trait STATUS;
    object WHITE extends STATUS;
    object GRAY extends STATUS;
    object BLACK extends STATUS;
    
    val matrix: Array[List[Node]] = new Array[List[Node]](n).map(e => Nil);
    
    def add(src: Int, dst: Int, weight: Int): Unit = matrix(src) = Node(dst, weight) :: matrix(src);
    
    def shortestPath(start: Int): (Array[Int], Array[Int]) = {
        val colors: Array[STATUS] = new Array[STATUS](n).map(e => WHITE);
        val parents = new Array[Int](n);
        val distances = new Array[Int](n).map( e => Int.MaxValue);
        val pq = new PriorityQueue[Int, Int](n * n, (a, b) => a > b);
        var blackCnt = 0;
        @tailrec
        def _shortestPath(): Unit = if (blackCnt < n) pq.dequeueOption match {
            case None =>();
            case Some((minWt, minIdx)) => {
                if (colors(minIdx) != BLACK) {
                    blackCnt += 1;
                    colors(minIdx) = BLACK;
                    matrix(minIdx).foreach { e =>
                        val dstIdx = e.idx;
                        val dstWt = e.weight;
                        if (colors(dstIdx) != BLACK) {
                            val newMinWt = minWt + dstWt;
                            if (newMinWt < distances(dstIdx)) {
                                distances(dstIdx) = newMinWt ;
                                colors(dstIdx) = GRAY;
                                parents(dstIdx) = minIdx;
                                pq.enqueue(newMinWt, dstIdx);
                            }
                        }
                    }
                }
                _shortestPath();
            }
        }
        parents(start) = -1;
        distances(start) = 0;
        pq.enqueue(0, start);
        _shortestPath();
        (distances, parents);
    }
    
}
class PriorityQueue[A, B](n: Int, lt: (A, A) => Boolean) {
    case class Node(key: A, value: B);
    
    val size = n + 1;
    var cnt = 0;
    val heap = new ArraySeq[Node](size);
    
    def isEmpty: Boolean = cnt == 0;
    
    def isFull: Boolean = cnt == n;
    
    def sort(): List[(A, B)] = (0 until cnt).foldLeft[List[(A, B)]](Nil) { (seq, i) => dequeue :: seq}.reverse;
        
    def dequeueOption(): Option[(A, B)] = Option(dequeue);
        
    def dequeue(): (A, B) = isEmpty match {
        case true => null;
        case false => {
            val top = heap(1);
            heap(1) = heap(cnt);
            cnt -= 1;
            heapify(1);
            (top.key, top.value);
        }
    }
    
    def enqueue(key: A, value: B): Boolean = {
        @tailrec
        def _enqueue(curr: Int): Unit = {
            val parent = if (curr % 2 == 0) curr / 2 else (curr - 1) / 2;
            if (parent > 0 && lt(heap(parent).key, heap(curr).key)) {
                swap(parent, curr);
                _enqueue(parent);
            }
        }
        isFull match {
            case true => false;
            case false => {
                cnt += 1;
                heap(cnt) = Node(key, value);
                _enqueue(cnt);
                true;
            }
        }
    }

    @tailrec
    private def heapify(index: Int): Unit = {
        val left = index * 2;
        val right = index * 2 + 1;
        if (right <= cnt) {
            val m = max(index, left, right);
            if (m != index) {
                 swap(m, index);
                heapify(m);
            }
        } else if (left <= cnt) {
            if (lt(heap(index).key, heap(left).key)) {
                swap(left, index);
            }
        }
    }
    
    private def max(c: Int, l: Int, r: Int): Int = {
        val curr = heap(c).key;
        val left = heap(l).key;
        val right = heap(r).key;
        if (lt(curr, left)) {
            if (lt(left, right)) r else l;
        } else {
            if (lt(curr, right)) r else c;
        }
    }
    
    private def swap(idx1: Int, idx2: Int): Unit = {
        val tmp = heap(idx1);
        heap(idx1) = heap(idx2);
        heap(idx2) = tmp;
    }
    
}



Measured memory_bytes: 49048