Saurabh recently did a project on HA-Linux in which he was given a task to configure it on a computer cluster. Each node/server in the cluster was assigned some kind of priority so as to form a hierarchy like structure. Assume we need to provide continuous services of IIT Mandi's website to the clients.
After configuring HA- Linux on a bunch of computers or cluster, he now thinks of measuring the response time of any number of servers to pick up the web application which was initially running on some other server(at the top level of hierarchy) before it fails. Let n be the number of nodes/server in the cluster. Each node is assigned a number from 1 to n (inclusive). Let a and b be two nodes of the cluster and ti be the response time when either one fails with respect to other. Let m be the number of queries for which response times between the two nodes are measured.
Now your task in this question is to find the subset of nodes such that every node is reachable or connected to every other node in the cluster and there must only be single way to establish connection between every pair of nodes. Finally, you have to output the minimum sum of the response times among all directly connected nodes in the sub-set chosen.
Note: It is not necessary that if node x is directly connected to node y and node y is directly connected to node z then node x is also directly connected to node y. Node x will be assumed to be connected to node z via node y.
Input :
The first line of input contains an integer T, the number of test cases. Then T test cases follow. Each test case consists of a line containing n, number of nodes, and m, number of queries, separated by single space. Then m lines follow. Each consists of 3 numbers – a, b and ti as described in the problem statement and separated by single space.
Output :
Output on a new line the minimum sum of the sub-set (round to 2 decimal places)of nodes chosen.
Constraints :
1 <= T <=10
1 < n <= 250
n-1 <= m <= nC2
ti - floating point integer , less than 100.00 (ms)
