M. Антинаучная задача
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
128 мегабайт
ввод
input.txt
вывод
output.txt
Главная сила в человеке — это сила духа...
Юрий Гагарин

Обычный полёт на Марс с использованием топливных двигателей занял бы несколько лет. Понятно, что учёным не хотелось бы ждать так долго, поэтому у них был план. Не так давно астрономами СГАУ был открыт принципиально новый способ перемещения, основанный на пространственных разломах. В определённых областях необъятной Вселенной имеются так называемые провалы в пространстве, позволяющие вопреки законам теории относительности перемещаться на огромные расстояния за пренебрежимо малое время. Такие области учёные назвали кротовыми норами. Две кротовые норы могут быть не соединены вообще, соединены гиперпространственным переходом, либо соединены нуль-переходом, причём такие соединения могут быть односторонними. В любом случае, добравшись до одной из кротовых нор, космический корабль сможет перемещаться между ними, затрачивая малое количество энергии. Если из одной норы в другую ведёт гиперпространственный переход, то переместиться между ними в заданном направлении космический корабль сможет за один античас. На корабле это перемещение действительно займёт примерно час. Если же из одной кротовой норы в другую ведёт нуль-переход, то корабль и вовсе может переместиться по нему без временных затрат: происходит мгновенный обмен участками пространства с другой норой.

Всего учёным известно положение $$$n$$$ кротовых нор и связи между ними. Все норы занумерованы. По плану космический корабль «Запад-1» доберётся до кротовой норы номер $$$1$$$, которая ближе всего находится к Земле, а дальше, перемещаясь по ним, будет стремиться попасть в нору номер $$$n$$$, которая находится ближе всего к Марсу. Теперь учёные хотели бы проложить маршрут перемещения между этими норами, чтобы время, потраченное космонавтами на перемещение, было минимальным. При этом учёные считают маршрут заведомо плохим, если корабль посещает одну и ту же нору дважды.

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

В первой строке входного файла содержится два целых числа через пробел: $$$n$$$ и $$$m$$$ ($$$1 \le n \le 10^5, 0 \le m \le 10^5$$$) — количество кротовых нор и количество известных связей между ними. В последующих $$$m$$$ строках содержится по 3 целых числа через пробел: $$$a_i$$$, $$$b_i$$$, $$$t_i$$$ — номера кротовых нор, соединенных переходом, и тип перехода (0 обозначает нуль-переход, 1 — гиперпереход). Гарантируется, что переход ни из какой норы не ведёт в неё саму, кроме того, из одной норы в другую напрямую может вести только один переход.

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

В первой строке выходного файла должны быть записаны 2 целых числа через пробел — количество античасов, которое будет затрачено космонавтами на путешествие, и количество кротовых нор $$$k$$$ в маршруте корабля. Во второй строке должно быть записано $$$k$$$ целых чисел — номера кротовых нор, которые должен посетить корабль. Если решений несколько, можно вывести любое из них. Если не существует способа добраться до нужной кротовой норы через переходы между ними, то в единственной строке выходного файла должно быть записано единственное слово «IMPOSSIBLE» без кавычек.

Примеры
Входные данные
9 11
1 2 1
1 3 1
2 4 1
2 5 1
3 5 1
3 6 1
4 9 1
6 9 1
5 7 0
7 8 0
8 9 0
Выходные данные
2 6
1 3 5 7 8 9
Входные данные
15 18
1 2 0
1 3 0
2 3 1
2 5 1
2 4 1
3 4 1
3 8 1
4 5 0
4 6 0
4 7 0
4 8 0
9 13 1
10 13 1
10 11 1
11 14 1
12 14 1
13 14 0
14 15 0
Выходные данные
IMPOSSIBLE