Description

There are $n$ mountains in the mountainous area. There are $m$ narrow mountain paths between the mountains. Each path connects two mountains, is one-way, and costs Xiao X a certain amount of time.

Xiao X is currently at mountain $1$. His goal is mountain $n$, because there is a train station there.

However, Xiao X’s stamina is limited. Each time he traverses a narrow mountain path, he becomes more tired, causing the time to traverse any narrow mountain path to increase by $1$.

Input Format

The first line contains two integers, $n, m$.

From line $2$ to line $m+1$, each line contains $3$ integers $A, B, C$, indicating that there is a narrow mountain path from $A$ to $B$ that allows Xiao X to move from $A$ to $B$ with a time cost of $C$.

Output Format

The first line contains an integer $T$, the shortest time Xiao X needs.

The second line contains a sequence of integers separated by spaces, representing Xiao X’s route. For example, [1, 4, 2, 5] means Xiao X starts from mountain 1, moves to mountain 4, then to mountain 2, and finally to mountain 5.

5 8
2 4 2
5 2 1
1 2 1
4 3 2
1 3 3
4 5 2
1 5 8
3 5 3

7
1 3 5 

Hint

Constraints

For all testdata, $n \le 10^4$, $m \le 2 \times 10^5$.

The testdata guarantees that the shortest path is unique.

Translated by ChatGPT 5