import scala.reflect.ClassTag;
import scala.io.StdIn.{readInt, readLine};

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 dstCnt = line(1);
            (0 until dstCnt).foldLeft(line.drop(2).toList) { (dsts, i) =>
                dsts match {
                    case dst :: cost :: rest => ig.add(src, dst, cost); rest;
                    case _ => dsts;
                }
            }
        }
        val (d, p) = ig.shortestPath(0);
        for(i <- (0 until n)) {
            println("%d %d".format(i, d(i)));
        }
    }
}

class IntGraph(size: Int) {
    val matrix: Array[List[(Int, Int)]] = new Array[List[(Int, Int)]](size).map( e => Nil);
    
    def add(src: Int, dst: Int, cost: Int): Unit = matrix(src) = (dst, cost) :: matrix(src);
    
    def shortestPath(from: Int): (Array[Int], Array[Int]) = {
        val colors = new Array[Int](size); // 0: 未追加, 1: 追加済み
        val distances = new Array[Int](size).map(e => Int.MaxValue);
        val parents = new Array[Int](size);
        implicit val ord: Ordering[(Int, Int)] = Ordering.by((e: (Int, Int)) => e._2).reverse;
        val pq = new PriorityQueue[(Int, Int)]();
        def _shortestPath: Unit = {
            pq.dequeue match {
                case None => ();
                case Some((src, cost)) => {
                    if (colors(src) != 1) {
                        colors(src) = 1;
                        matrix(src).foreach { e =>
                            val dst = e._1;
                            val newCost = e._2 + cost;
                            if (newCost < distances(dst) && colors(dst) != 1) {
                                distances(dst) = newCost;
                                parents(dst) = src;
                                pq.enqueue((dst, newCost));
                            }
                        }
                    }
                    _shortestPath;
                }
            }
        }
        distances(0) = 0;
        parents(0) = -1;
        pq.enqueue((0, distances(0)))
        _shortestPath;
        (distances, parents);
    }
}

class PriorityQueue[A](implicit ord: Ordering[A], m: ClassTag[A]) {
    import ord._;
    private var heap: Array[A] = m.newArray(10000);
    private var size = 0;
    
    def isEmpty: Boolean = size == 0;
    
    def isFull: Boolean = size == heap.length;
    
    def enqueue(elem: A): Unit = {
        def _enqueue(curr: Int): Unit = {
            val parent = if (curr % 2 == 0) (curr - 2) / 2 else (curr - 1) / 2;
            if (parent >= 0 && heap(curr) > heap(parent)) {
                swap(curr, parent);
                _enqueue(parent);
            }
        }
        if (isFull) extendsArray;
        heap(size) = elem;
        _enqueue(size);
        size += 1;
        
    }
    
    def dequeue(): Option[A] = {
        if (isEmpty) {
            None;
        } else if (size == 1) {
            size -= 1;
            Some(heap(0));
        } else {
            val top = heap(0);
            heap(0) = heap(size - 1);
            size -= 1;
            heapify(0);
            Some(top);
        }
    }
    
    private def heapify(from: Int): Unit = {
        val left = from * 2 + 1;
        val right = from * 2 + 2;
        if (right < size) {
            val maxIdx = max(from, left, right);
            if (maxIdx > from) {
                swap(from, maxIdx);
                heapify(maxIdx);
            }
        } else if (left < size && heap(left) > heap(from)) {
            swap(from, left);
        }
    }
    
    private def swap(a: Int, b: Int): Unit = {
        val tmp = heap(a);
        heap(a) = heap(b);
        heap(b) = tmp;
    }
    
    private def max(curr: Int, left: Int, right: Int): Int = {
        if (heap(curr) > heap(left)) {
            if (heap(right) > heap(curr)) right else curr;
        } else {
            if (heap(right) > heap(left)) right else left;
        }
    }
    
    private def extendsArray(): Unit = {
        val tmp = m.newArray((heap.length * 1.5).toInt);
        heap.copyToArray(tmp);
        heap = tmp;
    }
}


Measured memory_bytes: 246952