ACM Contest and Blackout
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 first line contains two numbers 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 a[i], b[i], c[i], where c[i] (1 ≤ c[i] ≤ 300) is the cost of the connection between schools a[i] and b[i]. The schools are numbered with integers in the range 1 to n.
Output
The output line should contain two numbers separated by a single space - the cost of two the cheapest connection plans. Let S[1] be the cheapest cost and S[2] the next cheapest cost. It’s important, that S[1] = S[2] if and only if there are two cheapest plans, otherwise S[1] ≤ S[2]. You can assume that it is always possible to find the costs S[1] and S[2].