You are given n cities and m bidirectional roads connecting them. Each road has a corresponding length . Emil, an adventurous traveler, wants to go from city 1 to city n using these roads. However, he has a twist in his plan - he will choose the shortest road among all the paths that are strictly longer than the overall shortest path.

In other words, your task is to help Emil determine the length of the second shortest path from city 1 to city n.

Input

The first line of the input contains two integers n and m, representing the number of cities and the number of roads, respectively.
The next m lines contain three integers , , and , indicating that there is a bidirectional road between city and city with length .

Output

Output a single integer representing the length of the second shortest path from city 1 to city n.