Background

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.

Problem Description

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$).

Input Format

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 Format

Output a single line with the shortest transmission time.

3 2
1 2 1
2 3 1

2

5 5
1 2 1
2 3 6
3 4 1
4 2 1
3 5 2

3

Hint

• 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