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

_ = gets

$graph       = {}
$open_list   = []
$closed_list = []

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)}
  $open_list.push(node_id)
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 =
    $visited_nodes
      .flat_map{|node_id|
        to_nodes = $graph[node_id]
        w        = $weights[node_id]
        to_nodes.map{|n| {id: n.id, weight: w + n.weight} }
      }
      .reject{|e| $visited_nodes.include?(e[:id])}
      .min_by{|e| e[:weight]}

  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}")
  }
