问网格图论

EN

我从几个小时开始尝试以下问题，但无法获得正确的逻辑。

您所在的规划团队负责规划辅助电网。这个辅助电网的目的是在断电的情况下为小城镇交叉口的灯柱供电。你的团队被赋予了k个生成器。您可以将这些发电机放置在电网中的任何位置，每个发电机都可以打开所有通过电网连接到它的灯(存在一条路径)。对于城镇中的每条道路，您将获得在网格中铺设电缆的成本，以连接该道路端点的两个交叉点。给定城镇的布局，您的任务是铺设成本最低的电网，并在其上安装发电机，以便您可以打开城镇交叉口的所有灯柱。

输入:第一行包含案例数t。然后，t个案例紧随其后。每种情况的第一行包含三个整数n、m和k。交叉点编号为1到n。然后，m行紧随其后。每条线包含三个整数i，j，c。整数i和j介于1和n之间，并表示道路两个端点的两个交叉点。第三个整数c是在这条道路的电网中铺设电缆的成本。

输出:您应该输出t行，每种情况一行。对于每种情况，输出最小成本网格。如果这个任务是不可能的(即没有办法用k个发电机打开所有的灯)，输出“不可能！”(为清楚起见，引用)

Constraints:
1 <= t <= 25
1 <= n <= 2000
0 <= m <= n(n-1)/2
0 <= c <= 1000000

Sample Input:
2
3 1 1
1 2 10
6 7 2
1 2 20
1 3 5
1 4 10
2 3 8
2 4 15
3 4 2
5 6 9

Sample Output:
Impossible!
24

说明:在第一种情况下，连接点1和2与连接点3断开，并且不能仅使用一个发电机打开所有灯柱。你至少需要两个generators.In在第二种情况下，你可以在道路(1 3)、(2 3)、(3 4)和(5 6)上铺设电缆，然后在1号路口和5号路口各安装一台发电机。

如何有效地解决这个问题?对了，现在除了BruteForce，我没有别的想法了。修改后的Kruskal能在这里工作吗？