Gord is training for a marathon. Behind his house is a park
with a large network of jogging trails connecting water
stations. Gord wants to find the shortest jogging route that
travels along every trail at least once.
Input
Input consists of several test cases. The first line of
input for each case contains two positive integers:
$n\leq 15$, the number of
water stations, and $m \leq 1\,
000$, the number of trails. For each trail, there is one
subsequent line of input containing three positive integers:
the first two, between 1 and $n$, indicating the water stations at
the end points of the trail; the third indicates the length of
the trail, in cubits at most $10\, 000$. There may be more than one
trail between any two stations; each different trail is given
only once in the input; each trail can be travelled in either
direction. It is possible to reach any trail from any other
trail by visiting a sequence of water stations connected by
trails. Gord’s route may start at any water station, and must
end at the same station. A single line containing 0 follows the
last test case.
Output
For each case, there should be one line of output giving the
length of Gord’s jogging route.
Sample Input 1 
Sample Output 1 
4 5
1 2 3
2 3 4
3 4 5
1 4 10
1 3 12
0

41
