P2121 Removing Carpets

Do you remember "Paving Carpets" from NOIP 2011 Senior Day 1? Time flies; three years have passed. The carefully prepared award ceremony is long over, leaving behind the carpets people walked on. Please solve another problem similar to "Paving Carpets."

There are $n$ key areas in the venue, and different key areas are connected by $m$ undirected "carpets." Each carpet is represented by three integers $u$, $v$, and $w$, where $u$ and $v$ are the indices of the two key areas connected by this carpet, and $w$ is its beauty value. Since the ceremony has ended, the laid carpets must be removed. To follow the principle of thrift, the organizers are allowed to keep at most $K$ carpets, and in the graph formed by the kept carpets, there must be only one way to travel between any two mutually reachable points. In other words, the new graph must have no cycles. Now the organizers ask you to compute the maximum possible sum of beauty values of at most $K$ carpets.

The first line contains three positive integers $n$, $m$, and $K$. Each of the next $m$ lines contains three positive integers $u$, $v$, and $w$.

Output a single positive integer, the maximum possible sum of beauty values of these $K$ carpets.

Choosing carpets $1$, $2$, and $4$ gives a beauty sum of $10 + 9 + 3 = 22$. If you choose carpets $1$, $2$, and $3$, although the sum can reach $10 + 9 + 7 = 26$, key areas $1$, $2$, and $3$ would form a cycle, which is not allowed. Constraints: $1 \le n, m, K \le 10^5$. Translated by ChatGPT 5