Lineville is a city inwhich ~n~ houses are arranged in a line. To travel from 1 house to an adjacent house, it takes 1 minute. Fortunately, there are ~m~ transport services which take you from one house to another, taking a particular amount of time. These services exist in one direction, but not necessarily the other. What is the shortest time it takes to travel from house 1 to house ~n~.

Input

The first line contains the integer ~n~ and ~m~. The following ~m~ lines contains 3 integers: ~a, b, c~. There exists a transport service from house ~a~ to ~b~ which takes ~c~ minutes.

Output

Output the time in minutes to travel from house ~1~ to house ~n~.

Constraints

• ~1 \le a, b \le n \le 10000~
• ~1 \le m \le 1000~
• ~1 \le c \le 10^9~

Case 1

Input

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

Output

2

Case 2

Input

10 10
9 8 2
5 6 5
8 10 4
9 1 4
4 10 1
8 5 2
6 4 5
3 3 2
6 10 5
6 1 5

Output

4