$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)
  $heap = Hash.new
  $heap[0] = 0
  (1..$n-1).each{ |i| $heap[i] = INF }
  d = Array.new($n, INF)
  d[x] = 0
  while $heap.size > 0
    t = $heap.sort_by{ |k, v| v }[0][0]
    $heap.delete(t)
    $m[t].each do |r|
      u, w = r
      if d[t] + w < d[u]
        d[u] = d[t] + w 
        $heap[u] = d[u]
      end
    end
  end
  d
end
ret = dijkstra(0)
ret.each_index{ |i| puts "#{i} #{ret[i]}" }