Description

You are given the number of clouds $N$, and then $M$ relations indicating which clouds can be connected.

Now Xiaoshan wants to connect all clouds into exactly $K$ cotton candies (connected components). Each cotton candy must use at least one cloud. He wants to know how to connect them so that the total cost is minimized.

Input Format

The first line contains three integers $N, M, K$.

Each of the next $M$ lines contains three integers $X, Y, L$, meaning cloud $X$ and cloud $Y$ can be connected at a cost of $L$.

Output Format

Output one line containing a single integer, the minimum total cost.

If it is impossible to obtain exactly $K$ cotton candies, output No Answer.

3 1 2
1 2 1

1

Hint

Constraints:

• For $30\%$ of the testdata, $1 \le N \le 100$, $1 \le M \le 10^3$.
• For $100\%$ of the testdata, $1 \le N \le 10^3$, $1 \le M \le 10^4$, $1 \le K \le 10$, $1 \le X, Y \le N$, $0 \le L < 10^4$.

Translated by ChatGPT 5