import java.io.PrintWriter

data class Edge(val v: Int, val c: Int)

fun main(args: Array<String>) = with(PrintWriter(System.out)) {
    val n = readLine()!!.toInt()
    val edge = (0 until n).map {
        val tmp = readLine()!!.split(' ')
//            .drop(2)
            .map { it.toInt() }
//            .zipWithNext { v, c -> Edge(v, c) }
        (1..tmp[1]).map { i ->
            Edge(tmp[2*i], tmp[2*i+1])
        }
    }

    val d = IntArray(n) { Int.MAX_VALUE }
    val explored = mutableSetOf<Int>()
    val frontier = mutableSetOf<Int>()

    d[0] = 0
    frontier.add(0)
    while (frontier.isNotEmpty()) {
        val minV = frontier.minBy { d[it] }!!
        explored.add(minV)
        frontier.remove(minV)
        edge[minV].forEach {
            if (!explored.contains(it.v)) {
                if (d[it.v] > d[minV] + it.c) {
                    d[it.v] = d[minV] + it.c
                    frontier.add(it.v)
                }
            }
        }
    }

    d.forEachIndexed { index, i ->
        println("$index $i")
    }

    flush()
}

