Round Trip

There are N countries and M bidirectional roads. The countries are numbered from 1 to N, and a road can be traveled in either direction between the two countries it connects. You start in country 1.

For a summer trip, you want to go from country 1 to country N and then return to country 1. You have only one pass for each road, so the same road cannot be used twice during the whole trip. Find the minimum total time needed for this round trip.

The first line contains the number of countries N and the number of roads M. (3 <= N <= 1,000, 2 <= M <= 10,000)

Each of the next M lines contains three natural numbers A, B, and C describing one road. It means that countries A and B are connected by a road that takes C time to traverse. (1 <= A <= N, 1 <= B <= N, 1 <= C <= 50,000)

There is at most one road between any two countries. The input is always such that a valid round trip is possible.

Print the minimum total time required for the round trip on the first line.

For the given input, traveling in the order 1-2-4-3-1 takes total time 10. It is impossible to make a valid round trip in less than 10 time.