406839: GYM102569 D Lexicographically Minimal Shortest Path

You are given a connected undirected unweighted graph with $$$n$$$ vertices and $$$m$$$ edges. The graph does not contain self-loops and parallel edges. Additionally, on each edge $$$(u_i, v_i)$$$ the letter $$$c_i$$$ is written.

You have to find the shortest path from the vertex 1 to the vertex $$$n$$$, and if there are several such paths, to find the one which has the string formed by the letters of this path to be lexicographically minimal.

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 200000, 1 \le m \le 200000$$$) — the number of vertices and the number of edges in the graph.

Each of the next $$$m$$$ lines contains two integers $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n, u_i \ne v_i$$$) — the vertices connected by the $$$i$$$-th edge, and the lowercase Latin letter $$$c_i$$$ written on this edge.

In the first line output the integer $$$k$$$ — the length of the shortest path from the vertex 1 to the vertex $$$n$$$.

In the second line output $$$(k+1)$$$ integers — the sequence of vertices in the shortest path.

In the third line output the string with $$$k$$$ characters — the sequence of letters on this path. This string must be lexicographically minimal among all strings formed by shortest paths from vertex 1 to vertex $$$n$$$.

If there are several possible answers, output any of them.

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