class Priority_queue
  def initialize(bool = true)
    if bool
      @ope = proc{|a, b|(a and b)? a > b : false}
    else
      @ope = proc{|a, b|(a and b)? a < b : false}
    end
    @heap = []
  end

  def <<(other)
    @heap.push(other)
    up
  end

  def gets
    result = @heap.shift
    @heap.unshift(@heap.pop)
    down
    return result
  end
  
  def up(key = @heap.size - 1)
    if @ope.call(@heap[key / 2], @heap[key])
      @heap[key / 2], @heap[key] = @heap[key], @heap[key / 2]
      down(key / 2)
      up(key / 2)
    end
  end

  def down(key = 0)
    if @ope.call(@heap[key], @heap[key * 2]) and @ope.call(@heap[key * 2 + 1], @heap[key * 2])
      @heap[key], @heap[key * 2] = @heap[key * 2], @heap[key]
      down(key * 2)
    elsif @ope.call(@heap[key], @heap[key * 2 + 1])
      @heap[key], @heap[key * 2 + 1] = @heap[key * 2 + 1], @heap[key]
      down(key * 2 + 1)
    end
  end
  def inspect
    @heap
  end
end
class Node
  include Comparable
  attr_reader :cost, :id
  def initialize(id, cost)
    @id = id
    @cost = cost
  end
  def <=>(other)
    @cost <=> other.cost
  end
end

def main
  n = gets.to_i
  array = Array.new
  n.times do
    array << gets.split(" ").map(&:to_i)[1..-1]
  end
  queue = Priority_queue.new
  minimum = Array.new(n, 1 / 0.0)
  minimum[0] = 0
  nowcost = 0
  position = 0
  while nowcost < minimum.max
    array[position][0].times do |i|
      queue << Node.new(array[position][1 + 2 * i], array[position][2 + 2 * i] + nowcost) if minimum[array[position][1 + 2 * i]] > (array[position][2 + 2 * i] + nowcost)
    end
    position = queue.gets
    while minimum[position.id] < position.cost
      position = queue.gets
    end
    position, nowcost = position.id, position.cost
    minimum[position] = nowcost
  end
  minimum.each_with_index{|item, idx|puts "#{idx} #{item}"}
end
main