The Ideal Path

A new maze has opened at an amusement park. It has n rooms and m two-way corridors connecting the rooms. Each corridor is painted a color ci. The entrance of the maze is room 1 and the exit is room n.

A contestant in the maze-escape contest starts at room 1 and, until reaching room n, writes down the colors of the corridors they walk through, in order. The winner is decided as follows:

• First, the number of written colors must be as small as possible; that is, you must take a path that uses the fewest corridors.
• If several paths use the same number of corridors, the one who took the most ideal path wins. A path is called ideal if its sequence of colors is lexicographically smaller than that of every other such path.

Given the maze, write a program that finds the ideal path from room 1 to room n.

The first line contains the number of rooms n and the number of corridors m. (2 ≤ n ≤ 100,000, 1 ≤ m ≤ 200,000)

Each of the next m lines describes one corridor with three integers ai, bi, ci: ai and bi are the two rooms the corridor connects, and ci is its color. (1 ≤ ai, bi ≤ n, 1 ≤ ci ≤ 10^9)

Every corridor is bidirectional. There may be more than one corridor between the same pair of rooms, and there may be a corridor that returns to the same room (ai = bi). It is guaranteed that room n is always reachable from room 1.

On the first line, print the length of the shortest path from room 1 to room n (the number of corridors it uses).

On the second line, print the colors of the ideal path in order, separated by single spaces.

A sequence (a1, a2, ..., ak) is lexicographically smaller than a sequence (b1, b2, ..., bk) if there exists an index i such that ai < bi and aj = bj for every earlier position j < i.