Maximizing Carpet Beauty

There are n critical areas connected by m undirected carpets. Each carpet is described by three integers \(u\), \(v\), and \(w\), where \(u\) and \(v\) are the indices of the connected areas and \(w\) represents the beauty score of the carpet.

After the award ceremony, the carpets must be removed. However, to promote frugality, the organizers are allowed to retain at most \(K\) carpets, and the retained carpets must form a graph in which any two connected areas have exactly one unique simple path between them. In other words, the chosen carpets must form an acyclic graph (a forest).

Your task is to select at most \(K\) carpets such that the sum of the beauty scores is maximized while ensuring that adding any carpet does not create a cycle.

inputFormat

The first line contains three integers \(n\), \(m\), and \(K\) — the number of critical areas, the number of carpets, and the maximum number of carpets that can be retained, respectively.

Each of the following \(m\) lines contains three integers: \(u\), \(v\), and \(w\), representing a carpet connecting area \(u\) and area \(v\) with beauty score \(w\).

outputFormat

Output a single integer representing the maximum total beauty score achievable by selecting at most \(K\) carpets such that the resulting graph does not contain any cycles.

sample

4 4 2
1 2 4
2 3 3
3 4 2
4 1 1

7