Elon is looking into buying an electric car, however he is worried that it will affect his ability to go on long road trips. In particular, he is planning a road trip from Toronto to Vancouver this summer and he will need a car that can take him all the way there.

There are ~N~ cities with electric charging stations in North America and ~M~ roads between them. Elon can use a road only if it is shorter than the range of his electric vehicle. What is the minimum range that Elon's vehicle must have so that he could complete his road trip?

Input Specification

The first line of input contains two integers ~N, M~ ~(2 \le N, M \le 100~ ~000)~, the number of cities and roads, respectively. Cities are numbered from 1 to ~N~, with Toronto being city 1 and Vancouver being city ~N~. The next ~M~ lines each contain three integers ~A, B, L~ ~(1 \le A, B \le N, 1 \le L \le 10^9)~, which represent a road between cities ~A~ and ~B~ of length ~L~.

Output Specification

Output the minimum range that Elon's car must have in order for him to complete his road trip, or -1 if it is impossible for Elon to reach Vancouver.

Sample Input 1

3 2
1 2 100
2 3 200

Sample Output 1

200

Sample Input 2

3 3
1 3 500
1 2 400
2 3 400

Sample Output 2

400