class Node
  def initialize(id)
    @id = id
    @neighbors = []
    @visited = false
    @cost = -1
  end

  attr_accessor :id, :neighbors, :visited, :cost
end

def calc(nodes)
  nodes[0].visited = true
  nodes[0].cost = 0
  while (true) do
    visited_nodes = nodes.find_all {|key, value| value.visited == true}.map {|array| array[1]}
    return if visited_nodes.size == nodes.size
    
    next_node = [-1, 100001]
    visited_nodes.each do |v_node|
      v_node.neighbors.each do |neighbor|
        n_id = neighbor[0]
        n_dist = neighbor[1]
        if nodes[n_id].visited == false then
          cand_node = [n_id, v_node.cost + n_dist]
          next_node = cand_node if next_node[1] > cand_node[1]
        end
      end
    end

    next_id = next_node[0]
    next_cost = next_node[1]
    nodes[next_id].visited = true
    nodes[next_id].cost = next_cost

    nodes[next_id].neighbors.each do |neighbor|
      n_id = neighbor[0]
      n_dist = neighbor[1]
      if nodes[n_id].visited then
        cand_cost = next_cost + n_dist
        nodes[n_id].cost = cand_cost if nodes[n_id].cost > cand_cost
      end
    end
  end
end


# main
n = gets.chomp.to_i
vertices = {}
n.times do
  inputs = gets.chomp.split.map(&:to_i)
  neighbors = []
  2.step(2+inputs[1]*2-1, 2) do |i|
    neighbors << [inputs[i], inputs[i+1]]
  end
  vertices[inputs[0]] = Node.new(inputs[0])
  vertices[inputs[0]].neighbors = neighbors
end

calc(vertices)
vertices.sort_by {|key, value| key}.each do |id, node|
  puts "#{node.id} #{node.cost}"
end