Калейдоскопічний маршрут

У Калеїдостані є $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\ne u_i$; $0\le c_i\le 10^9$).

Кожна пара міст з'єднана не більше ніж однією дорогою. Гарантовано, що можна дістатися з будь-якого міста до будь-якого іншого міста, використовуючи дороги.

Вихідні дані

У першій строкі виведіть одне ціле число $k$ — кількість доріг у потрібному маршруті.

У другій строкі виведіть $k+1$ цілих чисел $c_0,c_1,\dots ,c_k$ — послідовність міст на маршруті ($1\le c_i\le n$; $c_0=1$; $c_k=n$).

Приклади

Примітка

У прикладі, наведеному в тесті, потрібний маршрут складається з $3$ доріг, і різниця між максимальною та мінімальною яскравістю його доріг дорівнює $8-2=6$.