Два кратчайших пути
Вчера Вася и Петя сильно повздорили и сегодня не хотя видеть друг друга у себя на пути в школу. Загвоздка в том, что они живут в одном доме, выходят в школу в одно и то же время и идут с одинаковой скоростью по кратчайшему пути. Никто из ребят не хочет менять свои привычки, и чтобы не идти вместе вдоль одной дороги, они хотят найти два разных кратчайших пути. Однако они могут встречаться в узлах дорожной сети, ибо кратковременная встреча не вызывает у них приступов раздражения.
Ребята просят вас помочь им. Для этого они занумеровали узлы числами от 1 до N. Их дом и школа стоят в узлах с номерами 1 и N соответственно. Между парой узлов может быть не более одной дороги.
Входные данные
Первая строка содержит целые числа N и M (2 ≤ N ≤ 400), где M — число дорог, которое заметили Петя и Вася. Каждое из следующих M строк содержит по три целых числа: X, Y и L (1 ≤ X, Y ≤ N, 1 ≤ L ≤ 10000), где X и Y — номера узлов, соединенных дорогой и длина дороги.
Выходные данные
В первую строку выведите номера узлов первого кратчайшего пути. Во вторую — второго. Если решения не существует, выведите "No solution" (без кавычек).