Woburn Challenge 2001

The mind reader had no thoughts on the last Survivor. To salvage a bleak situation, M makes the following decision. As her last act as chief (before she is fired for losing the pool), she will mobilize a multinational commando unit from the Delta Force, GIGN, Mossad, SAS, and Task Force 2 and engage them in an operation quarterbacked by her 2nd best agent, Austin Powers. The force will perform a great service to humanity by removing Jerri from the list of applicants who applied to be on Survivor. Clearly, this requires time travel. However, time travel has changed somewhat and it turns out that only certain time periods can be reached. Moreover, only certain time conduits exist that allow travel between certain two time periods. The final problem is that the time machine needs to be hardwired with the subspace parameters of these conduits, with each conduit costing a different amount to hardwire. (Note that the conduits are bi-directional and that there may be multiple conduits connecting time periods, each costing different amounts).

Times are tough and you want to build the time machine of minimum cost, but still want to be able to reach all the time periods from any time period (possibly by stopovers at other time periods). If it isn't possible to reach all time periods, then output Requires more conduits.

Input Specification

The first line contains ~T~, the number of test cases to follow.
The first line of each test case contains ~N~ ~(2 \le N \le 100)~, the number of time periods, and ~C~ ~(0 \le C \le 10\,000)~, the number of conduits.
The remaining ~C~ lines of this test case each contain three integers ~i~, ~j~, ~k~ indicating that there is a conduit connecting time periods ~i~ and ~j~ ~(i \ne j)~, with a cost of ~k~ ~(1 \le k \le 300)~.

Output Specification

For each test case, output the minimum cost to connect all time periods, or Requires more conduits if it is not possible to connect them all.

Sample Input

3
5 5
1 2 1
2 3 2
3 4 3
4 5 4
5 1 5
6 9
1 5 6
1 6 2
2 3 7
2 5 1
1 2 9
3 5 4
2 6 3
2 4 4
1 3 6
4 4
1 2 82
2 3 1
1 2 12
3 1 31

Sample Output

10
14
Requires more conduits