Задача №3706. Immediate Delivery
Вася и Петя работают курьерами в фирме "Мгновенная доставка". Сегодня им надо доставить огромное количество посылок по всему городу.
Транспортная система города, в котором они работают, состоит из перекрестков и дорог, их соединяющих. Все дороги двунаправленны и можно добраться по дорогам от любого перекрестка до любого.
Вася и Петя должны посетить все перекрестки, чтобы доставить посылки. Они хотят разделить все задание на две части так, чтобы минимизировать время последней доставки.
Офис компании "Мгновенная доставка" расположен на перекрестке номер 1.
В первой строке заданы целые числа n (1 ≤ n ≤ 18) и m - количество пунктов и дорог.
Следующие m строк описывают дороги. Каждая дорога задается тремя целыми числами: номерами перекрестков xi и yi, которые она соединяет, (1 ≤ x i, yi ≤ n) и временем ti, которое нужно, чтобы по проехать по ней (1 ≤ ti ≤ 1000). Между каждой парой перекрестков не более чем одна дорога. Никакая дорога не соединяет перекресток с самим собой.
В первой и единственной строке выведите минимальное время, за которое может быть осуществлена доставка.
6 6 1 2 10 2 3 10 3 4 5 4 5 10 5 6 20 2 5 10
40 4 1 2 3 4 3 3 1 2 5 6