Marshmallow Clouds

You are given N clouds and M possible connections among them. Each connection is represented by three integers \(u\), \(v\) and \(w\), meaning that cloud \(u\) and cloud \(v\) can be connected with a cost of \(w\). You are also given an integer K.

Your task is to partition the \(N\) clouds into exactly \(K\) groups (each group forms a "marshmallow") such that each marshmallow consists of clouds that are connected (directly or indirectly) using a subset of the given connections. Each marshmallow must contain at least one cloud. The cost to form a marshmallow is the sum of the costs of the connections used to connect its clouds. Find the minimum total cost required to form exactly \(K\) marshmallows.

If it is impossible to form exactly \(K\) marshmallows using the available connections, output -1.

Hint: This problem is equivalent to selecting a set of edges that forms a forest with exactly \(K\) connected components and minimizes the sum of the costs. A common approach is to first compute the Minimum Spanning Forest (MSF) and then remove the \(K - c_0\) most expensive edges (where \(c_0\) is the number of connected components in the MSF) if \(K \ge c_0\). If \(K < c_0\), the answer is -1.

inputFormat

The input consists of:

1. One line containing three integers \(N\), \(M\) and \(K\) \( (1 \leq N \leq 10^5,\ 0 \leq M \leq 10^5,\ 1 \leq K \leq N)\).
2. M lines, each containing three integers \(u\), \(v\) and \(w\) \( (1 \leq u, v \leq N,\ 1 \leq w \leq 10^9)\) indicating that cloud \(u\) and cloud \(v\) can be connected with cost \(w\). The graph is undirected.

outputFormat

Output a single integer representing the minimum total cost required to form exactly \(K\) marshmallows. If it is impossible, output -1.

sample

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

3