object Main extends App {
    val scan = new java.util.Scanner(System.in)
    val n = scan.next().toInt
    
    val graph: Dijkstra.Graph = Array.fill(n)(List())

    for (_ <- 1 to n) {
      val u, k = scan.next().toInt
      graph(u) = (1 to k).toList
                .map(_ => Dijkstra.Edge(scan.next().toInt, scan.next().toInt))
    }

    Dijkstra.shortest_path(graph, 0,n-1).zip(0 until n)
      .map(t => t._2.toString ++ " " ++ t._1.toString)
      .foreach(println(_))
}

object Dijkstra {
    case class Edge(to: Int, cost: Long)
    type Edges = List[Edge]
    type Graph = Array[Edges]
    val inf = (1e9+7).toLong
    
    def shortest_path(graph: Graph, start: Int, goal: Int): Array[Long] = {
        val pq = new collection.mutable.PriorityQueue[(Long, Int)]
        val cost = Array.fill(graph.length)(inf)
        cost(start) = 0
        pq += ((cost(start), start))
        while (pq.nonEmpty) {
            val current_edge = pq.dequeue()
            if (cost(current_edge._2) < current_edge._1) {
            } else {
                for (tmp <- graph(current_edge._2)) {
                    val sumCost = current_edge._1 + tmp.cost
                    if (cost(tmp.to) > sumCost) {
                        cost(tmp.to) = sumCost
                        pq += ((cost(tmp.to), tmp.to))
                    }
                }
            }
        }
        cost
    }
}

