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

В Калеидостане есть $n$ городов, соединённых $m$ двусторонними дорогами. Города пронумерованы от $1$ до $n$. Каждая дорога имеет целое число, называемое яркостью.

Киану хочет путешествовать из города $1$ в город $n$. Он стремится выбрать самый короткий маршрут, то есть маршрут с наименьшим количеством дорог. Среди всех таких маршрутов он хочет выбрать калейдоскопический маршрут, то есть маршрут с наибольшей возможной разницей между максимальной и минимальной яркостью его дорог. Помогите Киану найти такой маршрут.

Входные данные

Первая строка содержит два целых числа $n$ и $m$ — количество городов и количество дорог ($2\le n\le 10^5$; $1\le m\le 2\cdot 10^5$).

Следующие $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$.