1089: Exhibition

Our city will hold a jewelry exhibition. The exhibition is so large that it consists of many rooms. Some rooms have connections to others. The map of the exhibition is shown as following. Rx represents Room x and the number near the line between Ra and Rb represents the distance between Room a and Room b. To improve safety of exhibition, the host of exhibition hires a group of guards for patrol. The guards are required to patrol on schedule. They will walk through all connections and then go back to the room they started. Some connections may be walked thought more than once. They want to walk as the short path as possible. Because the map is too complex to them and they can’t find the shortest path, so they ask for you help. Can you write a program to find a shortest patrol path for the guards?

The input file of your program contains more than one map. Each map starts with a line with two integers n (n≤100)and m separated by a space, n denotes the number of the rooms and m denotes the number of connections. And the next m lines are connections’ status shown above. Each line contains three integers a,b and d, separated by a space, which means the distance between Room a and Room b is d. A map with n=0 and/or m=0 ends the input file. There is no leading and trailing space in each line. And no blank lines between maps.

Your program should output the length of the shortest path for each map. You should output one solution for a line and no blank lines between solutions.

9 12
1 2 5
1 8 2
2 3 5
2 9 6
3 4 9
4 5 4
4 9 4
5 6 4
6 7 3
6 9 4
7 8 4
8 9 3
0 0

68