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 visited = new ArrayBuffer[Int]
    val nodes = new Array[Node](n)
    for(i<-0 until n) {
      dist(i) = Int.MaxValue
      nodes(i) = new Node(Int.MaxValue, 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) if !visited.contains(v(i*2+2))) {
        if(dist(v(i*2+2)) == Int.MaxValue) {
          dist(v(i*2+2)) = v(i*2+3) + dist(v(0))
          pq.remove(nodes(v(i*2+2)))
          pq.add(new Node(dist(v(i*2+2)), v(i*2+2)))

        } else if(v(i*2+3)+dist(v(0)) < dist(v(i*2+2))) {
          dist(v(i*2+2)) = v(i*2+3)+dist(v(0))
          pq.remove(nodes(v(i*2+2)))
          pq.add(new Node(dist(v(i*2+2)), v(i*2+2)))
        }
      }
      visited += v(0)
    }

    for(i<-0 until n) {
      println(i + " " + dist(i))
    }
  }
}