Magical Portals

In the mystical realm of Algorithmland, a wise wizard has discovered a series of magical portals connecting different cities. There are $N$ cities numbered from $1$ to $N$, and exactly $M$ portals. Each portal allows travel in one direction only, taking a certain amount of time.

The wizard's quest is to travel quickly from city $1$ to city $N$. Your task is to determine the minimum amount of time required to achieve this journey. If no valid route exists from city $1$ to city $N$, output $-1$.

Input Format

• The first line contains two space-separated integers, $N$ and $M$, where $N$ is the number of cities and $M$ is the number of magical portals.
• Each of the next $M$ lines contains three space-separated integers: $u$, $v$, and $w$. The integer $u$ denotes the starting city, $v$ denotes the destination city of the portal, and $w$ is the time (in minutes) it takes to travel through that portal.

Output Format

• Output a single integer: the minimum time required to travel from city $1$ to city $N$. If there is no possible route, output $-1$.

Examples

Input

4 4
1 2 5
2 3 10
1 4 100
3 4 5

Output

20

Input

3 1
2 3 4

Output

-1