406839: GYM102569 D Lexicographically Minimal Shortest Path

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Lexicographically Minimal Shortest Pathtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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.

Output

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.

ExamplesInput
3 2
1 2 a
2 3 b
Output
2
1 2 3 
ab
Input
3 3
1 3 z
1 2 a
2 3 b
Output
1
1 3 
z
Input
4 4
1 2 b
2 4 a
1 3 a
3 4 z
Output
2
1 3 4 
az

加入题单

上一题 下一题 算法标签: