Дан связный неориентированный невзвешенный граф из $$$n$$$ вершин и $$$m$$$ ребер. В графе отсутствуют петли и кратные ребра. Дополнительно на каждом ребре $$$(u_i, v_i)$$$ написана буква $$$c_i$$$.
Требуется найти кратчайший путь из вершины 1 в вершину $$$n$$$, а если таких путей несколько, то такой, чтобы строка, образованная из букв на ребрах этого пути, была лексикографически минимальной.
В первой строке даны два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 200000, 1 \le m \le 200000$$$) — количество вершин и ребер в графе.
В каждой из следующих $$$m$$$ строк даны два числа $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n, u_i \ne v_i$$$) — вершины, соединенные $$$i$$$-м ребром, и строчная латинская буква $$$c_i$$$, написанная на этом ребре.
В первой строке выведите целое число $$$k$$$ — длину кратчайшего пути из вершины 1 в вершину $$$n$$$.
Во второй строке выведите $$$(k+1)$$$ целых чисел — последовательность вершин на кратчайшем пути.
В третьей строке выведите строку из $$$k$$$ символов — последовательность букв на этом пути. Эта строка должна быть лексикографически минимальной среди всех строк, образованных кратчайшими путями из вершины 1 в вершину $$$n$$$.
Если существует несколько возможных ответов, выведите любой из них.
3 2 1 2 a 2 3 b
2 1 2 3 ab
3 3 1 3 z 1 2 a 2 3 b
1 1 3 z
4 4 1 2 b 2 4 a 1 3 a 3 4 z
2 1 3 4 az
