Майк и Джон - работники в Немедленной Доставке. Однажды их попросили доставить много пакетов по всему городу.
Транспортная система города, в котором они работают, состоит из перекрестков и дорог, соединяющих эти перекрестки. Все дороги являются двусторонними и все перекрестки связаны друг с другом (напрямую или косвенно).
Майк и Джон должны посетить все перекрестки чтобы доставить все пакеты. Они хотят разбить эту задачу на две части таким образом, чтобы минимизировать время последней доставки.
Первая строка содержит два целых числа 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.
В третьей строке следует вывести путь Джона в том же формате.