Два найкоротших шляхи
Вчора Вася і Петро сильно посварилися, і сьогодні вони не хочуть бачити один одного на своєму шляху до школи. Проблема в тому, що вони живуть в одному будинку, виходять до школи одночасно і йдуть з однаковою швидкістю по найкоротшому маршруту. Ніхто з них не бажає змінювати свої звички, тому, щоб не йти разом однією дорогою, вони хочуть знайти два різних найкоротших шляхи. Проте вони можуть зустрічатися у вузлах дорожньої мережі, оскільки короткочасна зустріч не викликає у них роздратування.
Хлопці просять вас допомогти їм. Для цього вони пронумерували вузли числами від 1 до N. Їхній будинок і школа знаходяться у вузлах з номерами 1 і N відповідно. Між парою вузлів може бути не більше однієї дороги.
Вхідні дані
Перша строка містить цілі числа N і M (2 ≤ N ≤ 400), де M — кількість доріг, які помітили Петро і Вася. Кожен з наступних M рядків містить по три цілі числа: X, Y і L (1 ≤ X, Y ≤ N, 1 ≤ L ≤ 10000), де X і Y — номери вузлів, з'єднаних дорогою, і L — довжина дороги.
Вихідні дані
У першому рядку виведіть номери вузлів першого найкоротшого шляху. У другому — другого. Якщо рішення не існує, виведіть "No solution" (без лапок).