ACM Contest and Blackout#1107
In preparation for "The First National School ACM Contest," the mayor of the city decided to provide all schools with a reliable power source (the mayor is very concerned about blackouts). To accomplish this, the "Future" power station and one school (it does not matter which one) must be connected; additionally, some other schools must also be connected to the network.
A school is considered to have a reliable power source if it is connected directly to the "Future" power station or to another school that already has a reliable power source. You are given the cost to connect some pairs of schools. The mayor wants to find the two cheapest connection plans. The cost of a plan is the sum of the costs of all connections included in it. Help the mayor find these two cheapest connection plans.
The first line contains two integers separated by a space: (3 \le n \le 100), the number of schools in the city, and , the number of available connections among them. Each of the following lines contains three integers a_i, b_i, c_i, where c_i (1 \le c_i \le 300) is the cost of connecting schools a_i and b_i. Schools are numbered from to .
Print two integers separated by a space — the costs of the two cheapest connection plans. Let S_1 be the cheapest cost and S_2 the next cheapest. If S_1 = S_2, then there exist two distinct cheapest plans; otherwise, S_1 \le S_2. You may assume that it is always possible to find such S_1 and S_2.
Example 1
Example 2