In order to prepare the “The First National ACM School Contest” (in 20??) the major of the city decided to provide all the schools with a reliable source of power. (The major is really afraid of blackoutsJ). So, in order to do that, power station “Future” and one school (doesn’t matter which one) must be connected; in addition, some schools must be connected as well. You may assume that a school has a reliable source of power if it’s connected directly to “Future”, or to any other school that has a reliable source of power. You are given the cost of connection between some schools. The major has decided to pick out two the cheapest connection plans – the cost of the connection is equal to the sum of the connections between the schools. Your task is to help the major — find the cost of the two cheapest connection plans. Input The Input starts with the number of test cases, T (1 < T < 15) on a line. Then T test cases follow. The first line of every test case contains two numbers, which are separated by a space, N (3 < N < 100) the number of schools in the city, and M the number of possible connections among them. Next M lines contain three numbers Ai, Bi, Ci, where Ci is the cost of the connection (1 < Ci < 300) between schools Ai and Bi. The schools are numbered with integers in the range 1 to N. Output For every test case print only one line of output. This line should contain two numbers separated by a single space – the cost of two the cheapest connection plans. Let S1 be the cheapest cost and S2 the next cheapest cost. It’s important, that S1 = S2 if and only if there are two cheapest plans, otherwise S1 < S2. You can assume that it is always possible to find the costs S1 and S2. Sample Input 2 58 1 3 75 3 4 51 2 4 19 3 2 95 2 5 42 5 4 31 129 3 5 66 9 14 124 188 2 8 11 328 897 871 796 932
2/2 347 364 762 4 6 14 459 5 6 10 Sample Output 110 121 37 37