object Main {
    def main(args: Array[String]) = {
        val inf = Int.MaxValue-100000
        val in = io.Source.stdin.getLines
        val v = in.next.toInt
        val g = Array.fill(v)(inf)
        val e = in.flatMap(x => {val y = x.split(" ").map(_.toInt); y.drop(2).grouped(2).map(y(0) +: _)}).toList
        g(0) = 0
        var flag = true
        while(flag) {
            flag = false
            for (b <- e) if (g(b(0)) + b(2) < g(b(1))) {g(b(1)) = g(b(0)) + b(2); flag = true}
        }
        g.zipWithIndex.foreach(p => println(p._2 + " " + p._1))
    }
}