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