G. Кефирчик по шагам

Та же задача про кефиропроводы, но теперь надо вывести и сам маршрут — последовательность планет от первой до $n$-й.

Маршрутов минимального времени может быть несколько; выведите лексикографически наименьший как последовательность номеров планет.

Первая строка содержит числа $n$ ($1 \le n \le 10^5$) и $m$ ($0 \le m \le 10^5$).

Далее идут $m$ строк с тройками $u$, $v$, $c$, где $c$ равно 1 или 2.

Если доставка невозможна, выведите $-1$.

Иначе в первой строке — наименьшее время, во второй — маршрут.