import java.util.PriorityQueue
import java.util.Comparator
import scala.io.StdIn.{readLine,readInt}
import scala.collection.mutable.ArrayBuffer

object Main {

  class Node(val cost:Int, val id:Int) { }

  class NodeComparator extends Comparator[Node] {
    def compare(node1:Node,node2:Node) = { node1.cost-node2.cost }
  }

  def main(args:Array[String]) = {
    val comp:Comparator[Node] = new NodeComparator()
    val n = readInt
    val pq = new PriorityQueue[Node](n, comp)
    val g = for(i<-0 until n) yield { readLine.trim.split(" ").map(_.toInt) }
    val dist = new Array[Int](n)
    val nodes = new Array[Node](n)
    pq.add(new Node(0,0))
    for(i<-1 until n) {
      dist(i) = 1000000
      nodes(i) = new Node(1000000, i)
      pq.add(nodes(i))
    }
    dist(0) = 0

    while(!pq.isEmpty()) {
      val nd = pq.poll()
      val v = g(nd.id)

      for(i<-0 until v(1)) {
        val j = i*2+2
        val k = i*2+3
        val alt = v(k) + dist(v(0))
        if(alt < dist(v(j))) {
          dist(v(j)) = alt
          pq.remove(nodes(v(j)))
          pq.add(new Node(dist(v(j)), v(j)))
        }
      }
    }

    println{
      { for(i<-0 until n) yield (i.toString + " " + dist(i).toString) }.mkString("\n")
    }
  }
}