In order to prepare for the Olympiad in Informatics, the mayor decided to provide all schools in the city with reliable power supply. To do this, it is necessary to conduct a power line from an alternative source of electricity “Maibuttya” to one of the schools in the city (it doesn’t matter which one), as well as to connect some schools with each other by power lines.
A school is considered to have a reliable power supply if it is directly connected to the Maibutcha source, or to one of those schools that has a reliable power supply.
The connection cost between some pairs of schools is known. The mayor of the city decided to choose one of the two most economical power supply schemes (the cost of the scheme is equal to the sum of the costs of connecting pairs of schools).
Write a program that calculates the cost of the two most cost-effective alternative power supply schemes for schools.
Input
The first line of the input file contains two natural numbers separated by a space: N (3 <= N <= 100), the number of schools in the city, and M – the number of possible connections between them. Each of the following M lines contains three numbers: Ai, Bi, Ci, separated by spaces, where Ci - cost of laying a power line (1 <= Ci <= 300) from school Ai to school Bi (i=1,2,…,N).
Output
The single line of the output file must contain two natural numbers S1 and S2 separated by a space &ndash ; the two lowest circuit costs (S1 <= S2). S1=S2 if and only if there are several least cost reliable power supply schemes.
It is guaranteed that there are two different reliable power supply schemes for the input data.
Examples
| # |
Input |
Output |
| 1 |
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
|
110 121 |