Xiao wang has a new car, so he wants to have a trip from his home to hefei, however, there is no road from his house directly to Hefei, so he has to go through a number of cities to get to hefei, his car takes one unit of time driving a unit distance at first, but his car will be slow after every city that he pass, so he will take one more unit of time to take a unit of distance after every city (that is, if he has passed k cities, then he needs k units of time to take a unit of distance, we think his home is the first city), can you tell him how to spend the least time to reach Hefei?

The first line contains two numbers n and m (0 < n ≤ 200, 0 < m < n×(n-1)/2 ), n is the number of city, 1 is xiaowang's home, n is hefei, m is the number of road, bi-directional edge, then the following m line contains 3 numbers x, y, z, means there is a road from x to y, the distance is z.(You can make sure that there is always a path exist between his home ande hefei).

The least time xiao wang must use from his home to hefei.