n = gets.to_i
w = Array.new(n).map { Array.new(n, Float::INFINITY) }
n.times do
  u, k, *v = gets.split
  (0..2 * k.to_i - 1).step(2) { |i| w[u.to_i][v[i].to_i] = v[i+1].to_i }
end

d = Array.new(n, Float::INFINITY)
d[0] = 0
p = Array.new(n, -1)
color = Array.new(n, "WHITE")
u = nil

while true
  mincost = Float::INFINITY
  (0..n-1).each do |i|
    if color[i] != "BLACK" && d[i] < mincost
      mincost = d[i]
      u = i
    end

    break if mincost == Float::INFINITY
    color[u] = "BLACK"

    (0..n-1).each do |v|
      if color[v] != "BLACK" && w[u][v] != Float::INFINITY
        if d[u] + w[u][v] < d[v]
          d[v] = d[u] + w[u][v]
          p[v] = u
          color[v] = "GLAY"
        end
      end
    end
  end
end

d.each_with_index do |weight, idx]
  puts "#{idx} #{weight}"
end
