P2330 [SCOI2005] Busy City

City C is a very busy metropolis, and its roads are heavily congested. The mayor decides to renovate some of the roads. The road network in city C is as follows: there are $n$ intersections in the city. Some pairs of intersections are connected by roads, and there is at most one road between any pair of intersections. These roads are bidirectional and connect all intersections directly or indirectly. Each road has a score $c$: the smaller the score, the more congested the road is and the more it needs renovation. However, the budget is limited, so the mayor wants to renovate as few roads as possible. The requirements are: 1. The renovated roads must connect all intersections directly or indirectly. 2. Subject to requirement 1, the number of renovated roads should be as small as possible. 3. Subject to requirements 1 and 2, among the renovated roads, the maximum score should be as small as possible. Task: As the city planning bureau, you should make the best decision and choose which roads should be renovated.

The first line contains two integers $n, m$, meaning there are $n$ intersections and $m$ roads. Each of the next $m$ lines describes a road with three integers $u, v, c$, meaning there is a road between intersections $u$ and $v$ with score $c$.

Output two integers $s, \mathit{max}$, meaning you selected $s$ roads, and the maximum score among the selected roads is $\mathit{max}$.

Constraints For all testdata, $1 \le n \le 300$, $1 \le c \le 10^4$, $1 \le m \le 8000$. Translated by ChatGPT 5