G. Пивной путь
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Народ в Пиволенде любит пить пиво. Знаете ли вы, что пиво здесь такое хорошее и сильное, что каждый раз, когда вы пьете его, ваша скорость снижается в десять раз по сравнению с вашей скоростью до его употребления?

Бирко живет в городе Пивграде, но хочет отправиться в город Пивбург. Вам дана дорожная карта Пиволенда и Вам надо найти для него самую быструю дорогу. Когда он начнет свое путешествие в Пивграде, его скорость будет равна 1. Придя в новый город, он всегда пробует стакан местного пива, что делит его скорость на 10.

Вопрос таков: за какое минимальное время он доберется до Пивбурга? Если есть несколько маршрутов с минимальным временем, выберите тот, что содержит наименьшее количество дорог. Если всё равно остается более одного маршрута, выберите любой из них.

Гарантируется, что из Пивграда в Пивбург будет вести не менее одного маршрута.

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

В первой строке входа содержится целое число N — количество городов в Пиволенде и целое число M — количество дорог в этой стране. Города пронумерованы от 0 до N - 1, где город 0— это Пивград, а город N - 1— это Пивбург. Каждая из следующих M строк содержит три целы числа, a, b (a ≠ b) и len. Эти числа обозначают, что есть двунаправленная дорога между городами a и b длины len.

  • 2 ≤ N ≤ 105
  • 1 ≤ M ≤ 105
  • 0 ≤ len ≤ 9
  • Между двумя городами не более одной дороги
Выходные данные

В первой строке должно быть записано наименьшее время, необходимое на то, чтобы перейти из Пивграда в Пивбург.

Во второй строке дожны быть записаны номера городов по дороге из Пивграда в Пивбург, занимающей наименьшее время.

В третьей строке выхода должны быть записаны номера городов на этом маршруте в порядке посещения, разделенные пробелами.

Примеры
Входные данные
8 10
0 1 1
1 2 5
2 7 6
0 3 2
3 7 3
0 4 0
4 5 0
5 7 2
0 6 0
6 7 7
Выходные данные
32
3
0 3 7