def sssp ms, n
  colors = Array.new(n){1} # 1:white, 2:gray, 3:black
  costs = Array.new(n){Float::INFINITY}

  costs[0] = 0
  colors[0] = 2

  while true
    min_cost = Float::INFINITY
    min_cost_i = nil
    colors.each_with_index do |color, i|
      if color == 2 && costs[i] < min_cost
        min_cost = costs[i]
        min_cost_i = i
      end
    end

    break unless min_cost_i

    colors[min_cost_i] = 3

    ms[min_cost_i].each_with_index do |m, i|
      if colors[i] != 3
        new_cost = min_cost + m
        costs[i] = new_cost if new_cost < costs[i]
        colors[i] = 2
      end
    end
  end

  costs
end

n = gets.chomp.to_i
ms = []
n.times do
  _, i, *paths = gets.split(' ').map(&:to_i)
  rows = Array.new(n){Float::INFINITY}
  (0..(i - 1)).each do |j|
    rows[paths[2 * j]] = paths[2 * j + 1]
  end
  ms << rows
end
costs = sssp(ms, n)
costs.each_with_index do |cost, i|
  puts "#{i} #{cost}"
end
