def dfs(bridges, current_island, unselectable_island, time)
  return time if bridges.empty?

  next_bridges = bridges.select do |a, b, t|
    a == current_island || b == current_island
  end
  return false if next_bridges.empty?

  ans = 99999999

  next_bridges.each do |next_bridge|
    # bomb
    rest_bridges = bridges.dup
    rest_bridges.delete(next_bridge)
    result_time = dfs(rest_bridges, current_island, nil, time)
    ans = result_time if result_time && result_time < ans

    # pass
    a, b, t = next_bridge
    next_island = (current_island == a) ? b : a
    next if next_island == unselectable_island
    result_time = dfs(bridges, next_island, current_island, time + t)
    ans = result_time if result_time && result_time < ans
  end

  ans
end

while true
  @n = gets.to_i
  break if @n == 0

  bridges = []
  (@n - 1).times do
    bridges.push gets.split.map(&:to_i)
  end
  puts dfs(bridges, 1, nil, 0)
end