MiliTown

Time Limit: 8 Seconds    Memory Limit: 131072 KB

Construction of MiliTown (a new town in MiliCity) is just finished and it’s time to provide some services for ease of living in town. There are lots of MiliBuildings in MiliTown and according to the plan of the project, each MiliBuilding must be accessible from any other MiliBuildings. This access may be direct or indirect (an indirect access between two MiliBuildings is a kind of access that there are some MiliBuildings between them). Government concerns a lot about air pollution and has chosen bicycle-exclusive line project as the first choice, but it seems there is a big problem with this town – a construction engineering mistake – there are some MiliBuildings that are not accessible from some other MiliBuildings!

Milad is invited to solve the problem in two phases. In the first phase, he must make a plan for a bicycle-exclusive line between all connected MiliBuildings with constraints below at the lowest possible cost:

· Bicycles can only navigate on roads.

· Each road has a specific cost to be facilitated with bicycle-exclusive line.

Phase two will begin one year after accomplishment of phase one. In this phase, Milad must make a plan to bring the access between all MiliBuildings in MiliTown using bicycles. Again it should cost as less as possible and obey the following rule:

· If there is no road-access between some MiliBuildings, it is allowed to destroy a road – which is not facilitated with bicycle-exclusive line in phase one – and reconstruct it between any other two MiliBuildings. Facilitation cost remains the same as it was before the destruction.

Input

There is a single integer t on the first line of the input denoting number of test cases.

The first line of each test case, contains two integers n and m, with 1 <= n <= 200000 and 1 <= m <= 200000, which, n indicates the total MiliBuildings and m is the number roads. This is followed by m lines. In the ith line, there are three integers a_i, b_i and c_i. a_i and b_i are numbers of two different MiliBuildings and c_i with 1 <= c_i <= 1000 is the cost of bicycle-exclusive line facilities in the road between a_i and b_i.

Output

For each test case, print a single line contains total bicycle facility cost (both phase one and phase two) and total number of road destructions separated by single space and print “Who were the engineers?!” (Without quotes) if there is no possible solution for the town.

Sample Input

2
5 4
1 2 10
1 3 3
2 3 4
4 5 1
6 4
1 2 10
1 3 3
2 3 4
4 5 1

Sample Output

18 1
Who were the engineers?!

Submit