ToNode = Struct.new(:id, :weight)

_ = gets

$graph       = {}

while (line = gets)
  node_id, _, *nodes = line.split(' ').map(&:to_i)
  $graph[node_id] = nodes.each_slice(2).map{|id, weight| ToNode.new(id, weight)}
end

$visited_nodes = []



$start_node_id = 0
# Min Distance '0' to `key`
$weights = {$start_node_id => 0}
$visited_nodes.push($start_node_id)


loop do
  # Node which should be visited
  next_visit_node = nil
  min_weight = Float::INFINITY

  $visited_nodes.each{|node_id|
    to_nodes = $graph[node_id]
    w        = $weights[node_id]
    to_nodes.each{|n|
      if !$weights.has_key?(n.id)
        weight = w + n.weight
        if weight < min_weight
          min_weight = weight
          next_visit_node = {id: n.id, weight: weight}
        end
      end
    }
  }

  if next_visit_node.nil?
    break
  end

  $visited_nodes.push(next_visit_node[:id])
  $weights[next_visit_node[:id]] = next_visit_node[:weight]
end

$weights
  .sort_by{|k, v| k}
  .each{|node, weight|
    puts("#{node} #{weight}")
  }

