Server Time: Tue Oct 23, 2018 8:38 pm
Welcome ( logout
1086 - Jogging Trails
  PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 32 MB

Robin is training for a marathon. Behind his house is a park with a large network of jogging trails connecting water stations. Robin wants to find the shortest jogging route that travels along every trail at least once.

For each case, there should be one line of output giving the length of Robin's jogging route.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains two positive integers n (2 ≤ n ≤ 15), the number of water stations, and m (0 ≤ 1000), 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. 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. Robin's route may start at any water station, and must end at the same station.

Output

For each case, print the case number and the minimum possible length of Robin's jogging route

Sample Input

Output for Sample Input

1

4 5

1 2 3

2 3 4

3 4 5

1 4 10

1 3 12

Case 1: 41

 


Problem Setter: Gordon V. Cormack
Special Thanks: Jane Alam Jan (Solution, Dataset)
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan