我正在尝试几个小时的以下问题，但无法获得正确的逻辑。
您在一个规划团队中，该团队负责布置辅助电网。这个辅助电网的目的是在停电的情况下为小镇路口的灯柱供电。你的团队有 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 断开连接，您无法仅使用一台发电机打开所有灯柱。您至少需要两台发电机。在第二种情况下，您可以在道路 (1 3)、(2 3)、(3 4) 和 (5 6) 上铺设电缆，然后在 1 号交叉路口安装一台发电机，然后在 1 号路口安装一台发电机。发电机在 5 号交界处。
如何有效地解决这个问题？现在除了BruteForce我一无所知。修改后的 Kruskal 会在这里工作吗？