Background

One day, Little Z accidentally saw Little X writing an advanced regular expression program. This program, composed only of the characters "0", "1", ".", and "*", could match the core code of all programs that passed on the OJ! Little Z was very curious and decided to hack into Little X's computer to obtain this advanced regular expression program.

Problem Description

In the Internet network, each computer is not directly connected one-to-one, but some computers have unidirectional network connections between them. This means that a connection from A to B does not necessarily imply a connection from B to A. Moreover, some connections are fast, while others are slow, so the time taken for data transmission varies. Additionally, if there is a connection from A to B and also from B to A, then A and B are actually within the same local network, allowing for local transmission with zero time cost.

Now, Little Z informs you about the entire network structure. He wants to know the shortest transmission time from his computer (numbered 1) to Little X's computer (numbered n).

Input Format

The first line contains two integers \( n \) and \( m \), representing the number of computers and the number of connection relations, respectively.

The next \( m \) lines each contain three integers \( u \), \( v \), and \( w \), indicating that the transmission time from computer \( u \) to computer \( v \) is \( w \).

Output Format

The output file should contain a single line with the shortest transmission time.

Sample Input and Output

Sample Input #1

3 2
1 2 1
2 3 1

Sample Output #1

2

Sample Input #2

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

Sample Output #2

3

Notes

• 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 be within the range of an int.

见题面 Input 部分

见题面 Output 部分