Background

Xiao X came to the mountains and enjoyed the pleasures of the forest. While he was happily forgetting his worries, he suddenly realized that the new semester was imminent.

Problem 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