Негайна доставка
Майк і Джон працюють у компанії Негайна Доставка. Одного разу їх попросили доставити велику кількість пакетів по всьому місту.
Транспортна система міста складається з перехресть і доріг, що їх з'єднують. Усі дороги двосторонні, і всі перехрестя з'єднані між собою (безпосередньо або через інші перехрестя).
Майк і Джон повинні відвідати всі перехрестя, щоб доставити всі пакети. Вони хочуть розділити це завдання на дві частини так, щоб мінімізувати час останньої доставки.
Вхідні дані
Перший рядок містить два цілі числа n (1 ≤ n ≤ 18) і m - кількість перехресть і доріг.
Наступні m рядків описують дороги. Кожен рядок містить три цілі числа: x_i і y_i (1 ≤ x_i, y_i ≤ n) - номери перехресть, з'єднаних дорогою, і t_i (1 ≤ t_i ≤ 1000) - час проїзду по ній. Будь-які два перехрестя з'єднані не більше ніж однією дорогою. Жодна дорога не з'єднує перехрестя саме з собою.
Офіс Негайної Доставки знаходиться на перехресті з номером 1.
Вихідні дані
У першому рядку слід вивести мінімальний можливий час, через який останній пакет може бути доставлений.
Другий рядок повинен містити шлях Майка: кількість доріг p, пройдених Майком, і номери p + 1 перехрестя в порядку їх відвідування, починаючи з перехрестя 1.
У третьому рядку слід вивести шлях Джона в тому ж форматі.