Once upon a time, Byteland was full of brilliant and genius computer programmers and algorithm experts. Programming contest was a great field for the programmers to test and show their talent. Now-a-days programming contest have been dried out in Byteland. Everyone is busy with different types of software development, mobile application development and gaming contest. Different sponsor provider and ministry of ICT of Byteland is funding different project to develop applications but not inspiring programming contests. On the other hand, honorable minister of road transportation ministry is having some trouble with highway repairment in Byteland, as all the highways has been seriously damaged again on last rainy season. People of different cities are demonstrating protest against him to repair all the highways of the country. But recently ministry of road transportation is facing money problems. So they have to think twice before repair a highway whether they will be able to finish the repairment with existing money. The minister of road transportation has come up with a plan. He will select a set of highways to repair such that no city will be connected with more than one repaired highway. He will select maximum possible highways to repair, but the money is the concern here and every highway has its own cost to be repaired. So he will select maximum possible highways to be repaired with total cost as minimum as possible. The minister of road transportation ministry thought this problem can be solved using computer software. He passed the problem to the champions of several software development and app development contests through the minister of ICT ministry. They are trying to solve the problem from then but still could not succeed. It is your chance to solve the problem and show the minister of ICT ministry how much programming contest is needed in Byteland to regain their pride in Information Technology. The country of Byteland consists of N cities and M highways, where each highway connects two different cities and has a cost to repair. Given the description of Byteland’s road transportation, find the minimum possible cost to repair maximum number of highways where each city is incident with at most one repaired highway. Cost of repairing is the sum of cost of all the repaired highways. Input Input starts with an integer, T (T ≤ 100) denoting the number of test cases. Each case starts with two integers, N (1 ≤ N ≤ 50) and M (0 ≤ M ≤ N ∗ (N − 1)/2). Each of the next M lines contains three integers u, v and c (1 ≤ u,v ≤ N, u ̸= v, 1 ≤ c ≤ 109) meaning that there is a highway between city u and v and c is the cost to repair the highway. No highway will be mentioned twice in a test case. Output For each case, print the test case number, starting from 1, and the minimum cost to repair maximum possible highways with the constraint given above. Sample Input 2 43 125 236 347 33
2/2 1 2 100 1 3 200 2 3 300 Sample Output Case 1: 12 Case 2: 100