P1195 Pocket's Sky

Xiaoshan sits in the classroom, looking through a pocket-like window at a pocket-like sky. Many clouds are floating there and look beautiful; Xiaoshan wants to pick a few of those lovely clouds and make cotton candy.

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.

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 one line containing a single integer, the minimum total cost. If it is impossible to obtain exactly $K$ cotton candies, output `No Answer`.

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