Республиканская олимпиада по информатике 2010 год, Кызылорда

Задача B. Путь

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

В стране $N$ городов. Перемещаться между ними можно только по дорогам, которые есть между некоторыми парами городов. Путем назовем список городов $A_1$, $A_2$, ... $A_K$, такой, что все города в нем различны, $K > 1$ и для всех $i < K$ есть дорога между городами $A_i$ и $A_{i + 1}$. У каждого пути есть длина — сумма длин всех дорог между соседними в пути городами. Упорядочим все возможные пути из города $1$ в город $N$ (то есть $A_1 = 1$, $A_K = N$) по увеличению их длины, а в случае двух путей одинаковой длины — их упорядочим в лексикографическом порядке. Найдите первые $2$ пути в этом списке (гарантируется, что путей будет не меньше $2$).

Формат входного файла

Первая строка входного файла содержит два целых числа $N$ — количество городов, $M$ — количество дорог ($1 \le N \le 20$, $0 \le M \le N(N - 1)$). Следующие $M$ строк содержат по три целых числа $S_i$, $T_i$, $C_i$ — номера городов, соединенных $i$-й дорогой и ее длина ($1 \le S_i, T_i \le N$, $S_i \ne T_i$, $1 \le C_i \le 100$). Числа в строках разделены пробелами.

Формат выходного файла

В выходной файл выведите $2$ строки — пути, как они идут в списке. Первое число в каждой строке — $K$ — количество городов в найденном пути, следующие $K$ чисел — номера городов в том порядке, в котором они идут в найденном пути. Числа в строках должны быть разделены пробелами.

Пример:

Вход

4 4
1 2 3
1 3 1
2 4 4
3 4 2

Ответ

3 1 3 4
3 1 2 4