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.