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