until (n = $<.gets.to_i).zero?
  e = n.times.map {$<.gets.split.map(&:to_i)}
  edges = (e.map {|a, b, c| [[a, b], c]} + e.map {|a, b, c| [[b, a], c]}).to_h
  h = Hash.new([])
  edges.keys.each {|a, b| h[a] += [b]}
  
  try = ->(start) {
    shortest = Hash.new(Float::INFINITY)
    done = h.keys.map {|k| [k, false]}.to_h
    shortest[start] = 0
    
    loop do
      u = nil
      h.each_key do |node|
        next if done[node]
        u = node if !u or shortest[node] < shortest[u]
      end
      break unless u
      done[u] = true
      
      h[u].each do |v|
        if (a = shortest[u] + edges[[u, v]]) < shortest[v]
          shortest[v] = a
        end
      end
    end
    
    shortest.values.sum
  }
  puts h.keys.map {|k| [try.(k), k]}.sort.first.reverse.join(" ")
end
