На острове Занзибар в городе Адельтон есть туристическое агентство. Оно решило предложить клиентам, помимо других туров, еще и экскурсию по городу. Чтобы заработать как можно больше, агентство приняло хитрое решение: найти для экскурсии кратчайший маршрут, начинающийся и заканчивающийся в одном и том же месте.

Ваша задача — написать программу, которая найдёт такой маршрут. В городе N перекрёстков, занумерованных от 1 до N, и M двусторонних дорог, занумерованных от 1 до M. Два перекрёстка могут быть соединены несколькими дорогами, но никакая дорога не соединяет перекрёсток с самим собой. Каждый экскурсионный маршрут полностью определяется последовательностью номеров дорог y₁, …, y_k, k ≥ 3. Дорога y_i (1 ≤ i ≤ k − 1) соединяет перекрёстки x_i и x_i+1, дорога y_k соединяет перекрёстки x_k и x₁. Все числа x₁, …, x_k должны быть различны. Длина экскурсионного маршрута равна сумме длин всех дорог, составляющих его, то есть L(y₁) + L(y₂) + … + L(y_k), где L(y_i) — длина дороги y_i (1 ≤ i ≤ k). Ваша программа должна найти маршрут наименьшей длины или сообщить, что это невозможно, поскольку в городе нет ни одного подходящего маршрута.

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

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