$n = gets.to_i
INF = 1 << 30
$mat = Array.new($n){ Array.new }
$n.times do
  l = gets.split.map(&:to_i)
  l[1].times{ |i| $mat[l[0]] << l[2*(i+1),2] }
end
def dijkstra(x)
  d = Array.new($n, INF)
  d[0] = 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))
    $mat[t].each do |item|
      u, len = item
      d[u] = d[t] + len if d[t] + len < d[u]
    end
  end
  d
end
ret = dijkstra(0)
ret.each_index{ |i| puts "#{i} #{ret[i]}" }