Anil has won a lottery trip to Hawaii. However, on the day of the flight, he overslept! To optimize his chances of catching his flight, he needs to reach the airport via the shortest route. He has asked for your help in determining the shortest route.

There are n blocks in the city (numbered 0 to n-1). Anil's home is located in block 0 and the airport is in block n-1. Therefore, Anil has to go from block 0 to block n-1. Roads in the city go from one block to another and are bidirectional. Moreover, some roads are longer than others. You are given the road network of the city and your job is to find out the length of the shortest route from Anil's home to the airport. If there does not exist any route to the airport, print -1.

Input

The first line of the input consist of 2 space separated integers n and m. n denotes the number of blocks and m denotes the total number of roads. m lines follow.

Each road is described by its two endpoints and the length. Thus, each line consists of 3 space separated integers a b w denoting that there is a road from block a to block b of length w.

Output

Output a single number denoting the length of the shortest route from block 0 to block n-1. If no route exists, print -1.

Constraints

You are given that all road lengths are positive and integral. (w > 0)

Example

Input:
5 5
0 1 10
2 3 2
0 2 10
1 4 10
0 4 1

Output:
1