P2299 Mzc and the PE Monitor's Battle

The fourth installment of mzc and djn.

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.

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 one line: the shortest time from $1$ to $n$.

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