car

Problem Description

There are N cities labelled from 1 to N connected with E roads and Rar the Cat wants to travel from city 1 to city N. Each road has a particular distance and Rar the Cat is intending to buy a car to travel the distance between the cities. The cars have a specific mileage (Eg. Can only travel up to 100 kilometers) and therefore can only travel between cities where the road between them if their roads is less than or equal to 100 kilometers long (Rar the Cat can refuel at each city).

Rar the Cat wants to know the minimum mileage the car should have in order to travel from city 1 to city N as a car with a lower mileage costs less! Do note that Rar the Cat do not need to travel the minimum distance from city 1 to city N.

Input

The first line of input consists of 2 integers, N followed by E.

The subsequent E lines of input consists of 3 integers each A, B and D. This means that there exist a bi-directional road from A to B with distance of D kilometers. A and B would be a valid city (from 1 to N) and D will fit into a 32-bit signed integer.

The input will not contain 2 roads between any pair of 2 cities and all cities are connected to one another via one way or another.

Output

A single integer, the mimimum mileage the car should have in kilometers.

Limits

Subtask 1 (25%): 0 < N, E ≤ 100

Subtask 2 (25%): 0 < N, E ≤ 1000

Subtask 3 (50%): 0 < N, E ≤ 1000000

Sample Testcase

Input:

5 7
1 2 10
1 5 10
2 3 10
3 4 2
4 5 10
1 4 1
3 5 1

2