Find The Shortest Path 2

You are given a map consisting of n cities and m bidirectional roads connecting these cities. Each road has a non-negative integer length denoted by . Your task is to the length of the shortest path between city 1 and city n.

Input

The first line contains two space-separated integers, n and m (), representing the number of cities and the number of roads, respectively.
The next m lines each contain three space-separated integers , , and , representing a road between cities and with length ().

Output

A single integer representing the length of the shortest path from city 1 to city n.

Examples

Input
Output
4 5 1 2 3 1 3 5 2 4 3 3 4 3 1 4 7
6
Β 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue