Lineville

Lineville is a city in which $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$

Example 1

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

2

Example 2

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

4