Description

mzc is very rich (just kidding). He has $n$ male servants (those who did the first three installments know this). But such a large number of male servants attracted our PE monitor (a short, chubby fellow), who wants to compete with mzc for them.

mzc is very angry and decides to duel him, but cat's stamina is indeed somewhat unstable, so he needs you to help him calculate the minimum required time.

Input Format

The first line contains two numbers $n, m$. $n$ means there are $n$ stops, and $m$ means there are $m$ roads.

Then follow $m$ lines, each with three numbers $a_i, b_i, c_i$, meaning that it takes $c_i$ time to go from stop $a_i$ to stop $b_i$. Note that the edges are bidirectional. That is, it also takes $c_i$ time to go from stop $b_i$ to stop $a_i$.

Output Format

Output one line: the shortest time from $1$ to $n$.

5 8
1 2 3
2 3 4
3 4 5
4 5 6
1 3 4
2 4 7
2 5 8
1 5 100

11

Hint

Constraints: $1 \le n \le 2500$, $1 \le m \le 2 \times 10^5$, $1 \le c_i \le 10^6$.

Time limit: $1$ s.

Translated by ChatGPT 5