$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)
  cost = Array.new($n, INF)
  cost[x] = 0
  used = Array.new($n)
  while true
    m = INF
    $n.times{ |i| m = cost[i] if !used[i] && m > cost[i] }
    break if m == INF 
    $n.times do |i|
      if m == cost[i]
        used[i] = true
        $m[i].each do |r|
          u, w = r
          cost[u] = cost[i] + w if cost[u] > cost[i] + w 
        end
      end
    end
  end
  cost
end
ret = dijkstra(0)
ret.each_index{ |i| puts "#{i} #{ret[i]}" }