Hide

# Jogging Trails

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

CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 4.6medium
Statistics Show