Jogging Trails

Time limit1sMemory limit128 MB

Summary

Find the shortest closed walk that traverses every undirected weighted edge at least once, where the walk may start at any vertex.

Level: Hard8 of 10
Topics: Graph, Shortest path, Dynamic programming, Bit manipulation
Solved: No attempts yet

Problem

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 length of the shortest jogging route that travels along every trail at least once. His route may start at any water station, but it must end at the same station it started from.

Input

The input consists of several test cases. The first line of each case contains two positive integers $n$ and $m$ : $n \le 15$ is the number of water stations, and $m < 1000$ is the number of trails. Each of the next $m$ lines describes one trail with three positive integers. The first two (each between $1$ and $n$ ) are the water stations at the two ends of the trail, and the third is the length of the trail in cubits. There may be more than one trail between the same pair of stations; each distinct trail appears exactly once in the input, and every trail can be travelled in either direction. It is possible to reach any trail from any other trail through a sequence of connected water stations (that is, the network is connected). A single line containing $0$ follows the last test case.

Output

For each test case, print a single line containing the length of Gord's shortest jogging route.

Examples3

Example 1

Input

Expected output

Example 2
Input
```
2 1
1 2 5
0
```
Expected output
```
10
```
Example 3
Input
```
3 3
1 2 1
2 3 2
3 1 3
0
```
Expected output
```
6
```