import scala.collection.mutable.ArraySeq;
import scala.annotation.tailrec;
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[Node](n * n)(Ordering.by((node: Node) => node.weight).reverse);
        var blackCnt = 0;
        @tailrec
        def _shortestPath(): Unit = if (blackCnt < n) pq.dequeueOption match {
            case None =>();
            case Some(Node(minIdx, minWt)) => {
                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(new Node(dstIdx, newMinWt));
                            }
                        }
                    }
                }
                _shortestPath();
            }
        }
        parents(start) = -1;
        distances(start) = 0;
        pq.enqueue(new Node(start, 0));
        _shortestPath();
        (distances, parents);
    }
}
class PriorityQueue[A](n: Int)(implicit ord: Ordering[A]) {
    import ord._;
    
    val size = n + 1;
    var cnt = 0;
    val heap = new ArraySeq[A](size);
    
    def isEmpty: Boolean = cnt == 0;
    
    def isFull: Boolean = cnt == n;
    
    def sort(): List[A] = (0 until cnt).foldLeft[List[A]](Nil) { (seq, i) => dequeue :: seq}.reverse;
        
    def dequeueOption(): Option[A] = if (isEmpty) None else Option(dequeue);
        
    def dequeue(): A = isEmpty match {
        case true => throw new NoSuchElementException("no element to remove from heap");
        case false => {
            val top = heap(1);
            heap(1) = heap(cnt);
            cnt -= 1;
            heapify(1);
            top;
        }
    }
    
    def enqueue(elem: A): Boolean = {
        @tailrec
        def _enqueue(curr: Int): Unit = {
            val parent = if (curr % 2 == 0) curr / 2 else (curr - 1) / 2;
            if (parent > 0 && heap(parent) < heap(curr)) {
                swap(parent, curr);
                _enqueue(parent);
            }
        }
        isFull match {
            case true => false;
            case false => {
                cnt += 1;
                heap(cnt) = elem;
                _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 (heap(index) < heap(left)) {
                swap(left, index);
            }
        }
    }
    
    private def max(curr: Int, lelft: Int, right: Int): Int = {
        if (heap(curr) < heap(lelft)) {
            if (heap(lelft) < heap(right)) right else lelft;
        } else {
            if (heap(curr) < heap(right)) right else curr;
        }
    }
    
    private def swap(idx1: Int, idx2: Int): Unit = {
        val tmp = heap(idx1);
        heap(idx1) = heap(idx2);
        heap(idx2) = tmp;
    }
    
}



Measured memory_bytes: 579412