It is a commonly known fact that software professionals are caffeine junkies, so our Tea Boy ( Jayant ) decided to launch a startup to deliver tea by taking online tea orders and deliver it within 15 minutes. He became so successful that he had a network of delivery boys to deliver tea orders anywhere.
Binny is one such delivery boy who works for Jayant. Everyday, Binny gets N tea orders which he has to deliver to N different locations. These locations are connected with each other through H bridges. To reach a certain destination , Binny has to use these bridges. He also has to pay a certain amount of toll tax in order to use a bridge but once he has paid the tax for a particular bridge , he can use it as many times as he likes without again paying for it. Now because Binny drives really fast , time spent delivering is not a concern but the money spent on taxes is. Find the minimum amount Binny has to spend in order to deliver all the tea orders.
Note:
1. A location can be connected with two or more highways.
2. You can assume the names of the location to be '1' , '2' … 'n'.
3. Binny can start his journey at any location on the graph.
4. No location is connected to itself using a bridge.
5. No two bridges will have the same endpoints.
Input:
First line contains T, the number of test cases.
Each test cases consists of the following:
First line contains N, the number of locations.
Second line contains H, the number of bridges.
The next H lines contains the two location connected by a bridge and the tax for that bridge.
Constraints:
1 ≤ T ≤ 10
2 ≤ N ≤ 1000
1 ≤ H ≤ 100000
0 ≤ tax ≤ 100000
Output:
For each test case, print the minimum amount to be paid by Binny on a new line.