E. Егор в республике Дагестан
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Егор — известный российский певец, рэпер, актёр и блогер, и наконец-то он решил дать концерт в солнечной республике Дагестан.

В республике есть $$$n$$$ городов, некоторые пары которых соединены $$$m$$$ односторонними дорогами без дополнительных условий. Иными словами, дорожная сеть Дагестана представляет собой произвольный ориентированный граф. Егор собирается прилететь в город $$$1$$$, проехать из него по дорогам вдоль некоторого пути до города $$$n$$$, дать в нём концерт и улететь.

Как и у любого артиста, у Егора есть множество недоброжелателей и слишком назойливых фанатов, поэтому ездить Егор и его команда будут только по безопасным дорогам. В Дагестане есть два типа дорог, чёрные и белые: по чёрным можно безопасно проехать только ночью, а по белым — только утром. Перед началом поездки менеджер Егора составляет расписание: он выбирает для каждого города его тип, чёрный или белый, и если команда посещает какой-то город, то уехать из него она сможет только по одной из дорог соответствующего типа. После определения расписания Егор выбирает любой маршрут из города $$$1$$$ в город $$$n$$$, причём из соображений безопасности этот путь должен быть кратчайшим. Менеджер Егора очень любит Дагестан и хочет задержаться здесь подольше, поэтому он попросил Вас составить такое расписание, чтобы из города $$$1$$$ в город $$$n$$$ не существовало пути вообще, или кратчайший путь был максимально возможной длины.

Путём является один город или последовательность дорог такая что начало каждой дороги в последовательности (кроме первой) является концом предыдущей. Егор может перемещаться вдоль пути, только если все его дороги безопасны.

Длиной пути называется количество дорог в нём. Кратчайшим путём называется путь минимальной длины.

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

Первая строка содержит числа $$$n$$$, $$$m$$$ ($$$1 \leq n \leq 500000$$$, $$$0 \leq m \leq 500000$$$) — количество городов и дорог, соответственно.

В $$$i$$$-й из следующих $$$m$$$ строк даны три целых числа — $$$u_i$$$, $$$v_i$$$ и $$$t_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$t_i \in \{0, 1\}$$$) — номера городов, соединяемых дорогой, и тип дороги ($$$0$$$ — ночная, $$$1$$$ — утренняя).

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

В первой строке выведите длину искомого пути (или $$$-1$$$, если можно подобрать расписание так, чтобы пути из $$$1$$$ в $$$n$$$ не существовало).

Во второй строке выведите искомое расписание — строку из $$$n$$$ целых чисел, где $$$i$$$-е число равно $$$0$$$, если из $$$i$$$-го города можно уехать только по ночным дорогам, и $$$1$$$, если только по утренним.

Если существует несколько решений, выведите любое из них.

Примеры
Входные данные
3 4
1 2 0
1 3 1
2 3 0
2 3 1
Выходные данные
2
011
Входные данные
4 8
1 1 0
1 3 0
1 3 1
3 2 0
2 1 0
3 4 1
2 4 0
2 4 1
Выходные данные
3
1101
Входные данные
5 10
1 2 0
1 3 1
1 4 0
2 3 0
2 3 1
2 5 0
3 4 0
3 4 1
4 2 1
4 5 0
Выходные данные
-1
11111
Примечание

В первом примере, если покрасить город $$$1$$$ в белый цвет, кратчайший путь будет состоять из одной дороги, $$$1 \rightarrow 3$$$. Иначе, независимо от цветов остальных городов кратчайший путь будет $$$1 \rightarrow 2 \rightarrow 3$$$.

Во втором примере город $$$3$$$ следует покрасить в чёрный цвет, а из города $$$2$$$ существуют дороги обоих цветов в город $$$4$$$. Обратите внимание: может существовать дорога, соединяющая город с самим собой.