Ідеальний шлях
Нова атракція "Лабіринт" відкрита в парку розваг New Lostland. Лабіринт складається з n кімнат, з'єднаних m проходами. Кожен прохід має певний колір c_i. Відвідувачі лабіринту починають свій шлях з кімнати номер 1, і їхня мета — дістатися до виходу, який знаходиться в кімнаті номер n.
Власники лабіринту планують провести конкурс завтра. Кілька учасників будуть стартувати з кімнати номер 1. Вони повинні дістатися до кімнати номер n, записуючи кольори проходів, через які вони проходять. Переможцем стане той, хто матиме найкоротшу послідовність кольорів. Якщо кілька учасників мають однакову довжину послідовності, переможець визначається за ідеальним шляхом. Шлях вважається ідеальним, якщо його послідовність кольорів є лексикографічно найменшою серед усіх найкоротших шляхів.
Андрій готується до конкурсу. Він здійснив політ на гелікоптері над New Lostland і зробив фотографію лабіринту. Ваше завдання — допомогти йому знайти ідеальний шлях з кімнати номер 1 до кімнати номер n, щоб він міг виграти конкурс.
Вхідні дані
Перша строка вхідного файлу містить цілі числа n та m — кількість кімнат і проходів відповідно (2 ≤ n ≤ 100000, 1 ≤ m ≤ 200000). Наступні m рядків описують проходи, кожен з яких визначається трьома цілими числами: a_i, b_i та c_i — номери кімнат, які він з'єднує, та його колір (1 ≤ a_i, b_i ≤ n, 1 ≤ c_i ≤ 10^9). Кожен прохід можна пройти в обох напрямках. Дві кімнати можуть бути з'єднані більше ніж одним проходом, може бути прохід з кімнати в саму себе. Гарантується, що можна дістатися до кімнати номер n з кімнати номер 1.
Вихідні дані
Перша строка вихідного файлу повинна містити k — довжину найкоротшого шляху з кімнати номер 1 до кімнати номер n. Друга строка повинна містити k чисел — кольори проходів у порядку, в якому їх потрібно пройти на ідеальному шляху.