Майк и Джон - работники в \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}. В третьей строке следует вывести путь Джона в том же формате.