Калейдоскопічний маршрут#11142
У Калеїдостані є міст, з'єднаних двосторонніми дорогами. Міста пронумеровані від до . Кожна дорога має ціле число, яке називається яскравістю.
Кіану хоче подорожувати з міста до міста . Він прагне обрати найкоротший маршрут, тобто маршрут з найменшою кількістю доріг. Серед усіх найкоротших маршрутів він хоче вибрати калейдоскопічний маршрут, тобто такий, де різниця між максимальною та мінімальною яскравістю доріг є максимально можливою. Допоможіть Кіану знайти такий маршрут.
Перший рядок містить два цілі числа та — кількість міст та кількість доріг (2 \le n \le 10^5; 1 \le m \le 2 \cdot 10^5).
-тий з наступних рядків містить три цілі числа v_i, u_i та c_i — індекси міст, з'єднаних -тою дорогою, та яскравість -тої дороги (1 \le v_i, u_i \le n; v_i \neq u_i; 0 \le c_i \le 10^9).
Кожна пара міст з'єднана не більше ніж однією дорогою. Гарантовано, що можна дістатися з будь-якого міста до будь-якого іншого міста, використовуючи дороги.
У першому рядку виведіть одне ціле число — кількість доріг у потрібному маршруті.
У другому рядку виведіть k+1 цілих чисел c_0, c_1, \ldots, c_k — послідовність міст на маршруті (1 \le c_i \le n; c_0 = 1; c_k = n).
Приклад 1
У прикладі, наведеному в тесті, потрібний маршрут складається з доріг, і різниця між максимальною та мінімальною яскравістю його доріг дорівнює 8-2=6.