P2169 Regular Expression

One day, student Xiao Z unexpectedly saw Xiao X write an advanced regular expression program. This regex is composed only of the characters "0", "1", ".", and "*", yet it can match the core code of all programs that get AC on the OJ! Xiao Z became very curious, so he decided to hack into Xiao X's computer to obtain this advanced regex program.

In the Internet, computers are not directly connected one-to-one. Instead, some computers have one-way network connections. That is, even if there is a connection from $A$ to $B$, there may not be a connection from $B$ to $A$. Moreover, some connections are fast while others are slow, so the transmission time differs across connections. In addition, if both the connection from $A$ to $B$ and the connection from $B$ to $A$ exist, then $A$ and $B$ are effectively in the same LAN and can communicate locally, with a transmission time of $0$. Now Xiao Z gives you the topology of the network. He wants to know the shortest transmission time from his computer (numbered $1$) to Xiao X's computer (numbered $n$).

The first line contains two integers $n, m$, meaning there are $n$ computers and $m$ connections. The next $m$ lines each contain three integers $u, v, w$, meaning the time to transmit information from computer $u$ to computer $v$ is $w$.

Output a single line with the shortest transmission time.

- For $40\%$ of the data, $1 \leq n \leq 10^3$, $1 \leq m \leq 10^4$. - For $70\%$ of the data, $1 \leq n \leq 5 \times 10^3$, $1 \leq m \leq 10^5$. - For $100\%$ of the data, $1 \leq n \leq 2 \times 10^5$, $1 \leq m \leq 10^6$. The answer is guaranteed to fit in the `int` range. Translated by ChatGPT 5