ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1004. Экскурсия

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
На острове Занзибар в городе Адельтон есть туристическое агентство. Оно решило предложить клиентам, помимо других туров, еще и экскурсию по городу. Чтобы заработать как можно больше, агентство приняло хитрое решение: найти для экскурсии кратчайший маршрут, начинающийся и заканчивающийся в одном и том же месте.
Ваша задача — написать программу, которая найдёт такой маршрут. В городе N перекрёстков, занумерованных от 1 до N, и M двусторонних дорог, занумерованных от 1 до M. Два перекрёстка могут быть соединены несколькими дорогами, но никакая дорога не соединяет перекрёсток с самим собой. Каждый экскурсионный маршрут полностью определяется последовательностью номеров дорог y1, …, yk, k > 2. Дорога yi (1 ≤ ik − 1) соединяет перекрёстки xi и xi+1, дорога yk соединяет перекрёстки xk и x1. Все числа x1, …, xk должны быть различны. Длина экскурсионного маршрута равна сумме длин всех дорог, составляющих его, то есть L(y1) + L(y2) + … + L(yk), где L(yi) — длина дороги yi (1 ≤ ik). Ваша программа должна найти маршрут наименьшей длины или сообщить, что это невозможно, поскольку в городе нет ни одного подходящего маршрута.

Исходные данные

Ввод состоит из T тестов (1 ≤ T ≤ 5). Первая строка каждого теста содержит два целых числа — количество перекрёстков N и количество дорог M (3 ≤ N ≤ 100; 3 ≤ MN · (N − 1)). Каждая из следующих M строк описывает одну дорогу. Она содержит три целых числа: номер первого перекрёстка a, номер второго перекрёстка b и длину дороги l (1 ≤ a, bN; ab; 1 ≤ l ≤ 300). Ввод заканчивается строкой, содержащей единственное число −1.

Результат

Каждая строка вывода должна содержать ответ на соответствующий тест. Строка должна содержать или текст «No solution.», если нельзя подобрать экскурсионный маршрут, или номера всех перекрёстков в кратчайшем экскурсионном маршруте в порядке, в котором их нужно проезжать (то есть числа x1, …, xk из определения экскурсионного маршрута), разделённые одиночными пробелами. Если существуют несколько экскурсионных маршрутов минимальной длины, выведите любой из них.

Пример

исходные данныерезультат
5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20
4 3
1 2 10
1 3 20
1 4 30
-1
1 3 5 2
No solution.
Источник задачи: Central European Olympiad in Informatics 1999