IITKESO207PA5Q2 - Flight

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

Added by:Programming Club, IITK
Date:2018-03-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2018-05-05 05:04:45
Blocks are numbered 0 to n-1. Airport is at block n-1.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.