URI Online Judge | 2683

Design Space

By Emílio Wuerges, UFFS BR Brazil

Time limit: 2

The engineers from UFFS are studying the possibility of of building underground tunnels everywhere in the campus. The places where the entrances will be built, as always, were already chosen by MEC (Brazil's ministry of education), and the tunnels must least directly to one entrance to another. Since the budget was already done, these rules cannot be changed.

The original project was very well made, and there was a gallery between each pair of entrances, that were made in a way they would not cross, and the cost of these galleries was already paid. However, with the recent budget cuts, it is now necessary to chose only a subset of these galleries, without changing them, in a way that there is only one path between each pair of entrances.

The challenge now is to know the least and the largest cost possible, to fit in the new budget.


The first line consists of a number 1 ≤ N ≤ 106 that is the number of galleries.

Each following line has three numbers representing a gallery, 1 ≤ U, V ≤ 103 e 1 ≤ W≤ 200. That are, respectively, entrance, exit and construction cost of the gallery.


The output consist of two lines, each with a single number.

The first one must have the maximum cost of the project and the second must have the minimum cost of the project.

Input Example Output Example

1 2 96
1 3 9
2 3 79


1 2 96
1 3 9
1 4 79
2 3 126
2 4 19
3 4 178