I wish that you remember king Basm and Koorosh from the contest of last year! But do not worry; I will introduce them to you, again! In ancient times, many territories were under the control of a powerful king called Basm. Basm is well-known in history because of his strange works and as a result, there are many history-lovers who wish to know more about him. Koorosh Esteghrarzadeh is one of them and he has worked hard to find a way to know more about Basm’s works. Recently, he managed to invent a Time MachineTM and traveled to the past to Basm time in order to be able to see and study his weird works thoroughly. Unfortunately, he has been caught by royal guard soldiers of Basm and is now in his prison. At the same time, Basm’s advisors suggested him to build a new city, named Avrenim, to improve the industry of his territories and they gave him the road map of the city. The advisors have designed the city such that all roads are unidirectional and there exists at least one path from each junction to any other junction in the city and there is not any road from a junction to itself. In addition, they estimated the time that construction of each road requires. Also, they told Basm the whole structure of the map is confidential and must stay unknown until the city completely constructed, because otherwise, it will not affect the industry that much. As Basm madly loves his wife, he likes to be with her all the times! Thus, he likes to work as less as possible and he decided to construct just some of the roads instead of all of them. Then, after constructing these roads, he wants to order his little brother to construct the remaining roads by just telling him the roads endpoints, but not their directions (to secure the whole structure of the map to some extent) and ordering him to choose the direction of the roads such that there exists at least one path from each junction to any other junction in the city. Now, he wants to select the roads (if required all of them!), which he should construct, with minimum sum of construction time such that after ending of construction, the resulted road map be exactly the same as the road map his advisors suggested him (in other words, his selection of the roads forces appropriate direction of the other roads to satisfy the constraint mentioned above). Now, Basm ordered Koorosh to solve this problem given the roads of the city and their construction time, if he wants to stay alive! Input The input begins with a positive integer T showing the number of test cases and then, T test cases follow. Each test case begins with a line containing two integers 0 < n ≤ 50 and m ≤ 1000 showing the number of junctions and roads respectively. Then, m lines come containing two integer h and t between 1 and n showing head and tail of a road and a positive real number c showing the construction time of this road. There is a blank line after each test case. Output For each test case, your program must output the minimum sum of construction times of the roads, which Basm must construct.The output should be precise to 4 decimal digits after floating point Sample Input 1 33 1 2 5.0 2 3 4.5 3 1 5.5
2/2 Sample Output 4.5000