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