Задачі
Немедленная доставка
Немедленная доставка
Майк и Джон - работники в \textit{\textbf{Немедленной Доставке}}. Однажды их попросили доставить много пакетов по всему городу.
Транспортная система города, в котором они работают, состоит из перекрестков и дорог, соединяющих эти перекрестки. Все дороги являются двусторонними и все перекрестки связаны друг с другом (напрямую или косвенно).
Майк и Джон должны посетить все перекрестки чтобы доставить все пакеты. Они хотят разбить эту задачу на две части таким образом, чтобы минимизировать время последней доставки.
\includegraphics{https://static.e-olymp.com/content/45/45eeb0069b571ddd1e0e44fda5c68d3d7c3206af.jpg}
\InputFile
Первая строка содержит два целых числа \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{18}) и \textbf{m} - количество перекрестков и дорог.
Следующие \textbf{m} строк описывают дороги. Каждая строка содержит три целых числа: \textbf{x_i} и \textbf{y_i} (\textbf{1} ≤ \textbf{x_i}, \textbf{y_i} ≤ \textbf{n}) - номера перекрестков, соединенных дорогой, и \textbf{t_i} (\textbf{1} ≤ \textbf{t_i} ≤ \textbf{1000}) - время проезда по ней. Любые два перекрестка соединены не более чем одной дорогой. Никакая дорога не соединяет перекресток сам с собой.
Офис Немедленной Доставки находится на перекрестке с номером \textbf{1}.
\OutputFile
В первой строке следует вывести минимальное возможное время, через которое последний пакет может быть доставлен.
Вторая строка должна содержать путь Майка: количество дорог \textbf{p}, пройденных Майком и номера \textbf{p + 1} перекрестка в порядке их посещения, начиная с перекрестка \textbf{1}.
В третьей строке следует вывести путь Джона в том же формате.
Вхідні дані #1
6 6 1 2 10 2 3 10 3 4 5 4 5 10 5 6 20 2 5 10
Вихідні дані #1
40 4 1 2 3 4 3 3 1 2 5 6