$n = gets.to_i
INF = 1 << 30
$m = Array.new($n){ Array.new }
$n.times do
  l = gets.split.map(&:to_i)
  (1..l[1]).each{ |i| $m[l[0]] << l[2*i, 2] }
end
def dijkstra(x)
  d = Array.new($n, INF)
  d[x] = 0
  v = Array.new($n){ |i| i }
  while v.size > 0
    a = Array.new($n, INF)
    v.each{ |i| a[i] = d[i] }
    t = v.delete(a.index(a.min))
    $m[t].each do |r|
      u, w = r
      d[u] = d[t] + w if d[t] + w < d[u]
    end
  end
  d
end
ret = dijkstra(0)
ret.each_index{ |i| puts "#{i} #{ret[i]}" }