Description

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.

Input Format

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 Format

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

5 4 3
1 2 10
1 3 9
2 3 7
4 5 3

22

Hint

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