| IME++ Starters Try-outs 2023 |
|---|
| Finished |
Recently, Calheiros has been really excited about Mr. Megamind's class on graphs, so much so that it's been the only thing on his mind. This has gotten so out of hand that it started seeping into his dreams, and one day into a nightmare of his. Trapped in this nightmare, the professor appeared in it and gave him a problem to solve in order to escape. However, due to him being in panic, he's unable to think straight in order to solve it.
The professor wants to connect $$$n$$$ cities together, by using some combination of $$$m$$$ roads that he's able to build. Each road will link two cities together, and it has a unique cost associated with it; the cost of each road is pairwise distinct. As such, the professor wants to know two things: what's the lowest amount that has to be spent to link all the cities and what's the largest direct distance between two cities after building the roads. Luckily, out of nowhere, you appear in this dream and are able to assist. Will you be able to save Calheiros from this nightmare?
The first line contains two integers, $$$n$$$ and $$$m$$$, $$$(2 \leq n \leq 10^5)$$$, $$$(n - 1 \leq m \leq min(3 \times 10^5, \frac{n \times (n - 1)}{2})$$$ — the number of cities and roads, respectively.
Each of the next $$$m$$$ lines will contain the description of a road. Each line contains three integers $$$u_i$$$, $$$v_i$$$, $$$c_i$$$, $$$(1 \leq u_i, v_i \leq n, u_i \neq v_i)$$$, $$$(1 \leq c_i \leq 10^9)$$$ — a road that can be built to connect cities $$$u_i$$$ and $$$v_i$$$ with cost $$$c_i$$$.
It is guaranteed that each $$$c_i$$$ is pairwise distinct and that you can form a connected graph with the roads given.
Print two lines of output. On the first line, print the total cost of building the roads. On the second line, print the largest distance between two cities.
4 5 1 2 4 2 3 6 1 3 8 3 4 10 4 2 7
17 2
You can easily see that if you choose the edges that connect the cities $$$(1, 2)$$$, $$$(2, 3)$$$, $$$(4, 2)$$$, all of the cities will be connected and the lowest cost has been used to connect them. Besides that, you can notice that the largest distance between two cities in this graph is two.
| Name |
|---|


