В Калейдостане есть $$$n$$$ городов, соединенных $$$m$$$ двунаправленными дорогами. Города пронумерованы от $$$1$$$ до $$$n$$$. Каждая дорога имеет целое число, называемое красочностью.
Киану хочет путешествовать из города $$$1$$$ в город $$$n$$$. Он хочет выбрать самый короткий маршрут — то есть маршрут с наименьшим количеством дорог. Среди всех самых коротких маршрутов он хочет выбрать калейдоскопический — то есть маршрут с наибольшей возможной разницей между максимальной и минимальной красочностями дорог. Помогите Киану найти такой маршрут.
Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ — количество городов и количество дорог ($$$2 \le n \le 10^5$$$; $$$1 \le m \le 2 \cdot 10^5$$$).
$$$i$$$-я из следующих $$$m$$$ строк содержит три целых числа $$$v_i$$$, $$$u_i$$$ и $$$c_i$$$ — индексы городов, соединенных $$$i$$$-й дорогой, и красочность $$$i$$$-й дороги ($$$1 \le v_i, u_i \le n$$$; $$$v_i \neq u_i$$$; $$$0\le c_i \le 10^9$$$).
Каждая пара городов соединена не более чем одной дорогой. Гарантируется, что можно путешествовать из любого города в любой другой, используя дороги.
В первой строке выведите одно целое число $$$k$$$ — количество дорог в требуемом маршруте.
Во второй строке выведите $$$k+1$$$ целых чисел $$$c_0, c_1, \ldots, c_k$$$ — последовательность городов на маршруте ($$$1 \le c_i \le n$$$; $$$c_0 = 1$$$; $$$c_k = n$$$).
6 8 1 5 2 5 2 5 3 5 4 1 3 10 3 4 6 4 5 7 4 6 8 2 6 1
3 1 5 4 6
В примере теста требуемый маршрут состоит из $$$3$$$ дорог, и разница между максимальной и минимальной красочностями дорог равна $$$8-2=6$$$.
| 2021-2022 ICPC NERC (NEERC), North-Western Russia Regional Contest (Northern Subregionals) |
|---|
| Закончено |
