AT_wupc_05.独立記念日

长久以来延续的 W 帝国即将迎来其历史的终结。由于众多少数部族的叛乱，帝国将被分裂为多个独立的国家。因此，帝国的一位领主面临着一个棘手的问题。请帮助他完成最后的任务。现给定 $N$ 个城市和 $M$ 条道路的信息。每条道路连接两个不同的城市，并且可以双向通行。每条道路的信息由两个不同城市的编号（$1$ 到 $N$）以及分割该道路所需的代价给出。需要注意的是，任意两个城市之间至多只有一条道路，并且图中至多只存在一个环。

请你求出，将 $N$ 个城市分割成至少 $K$ 个独立的组时，所需的最小分割代价。这里，两个组被认为是独立的，当且仅当它们之间没有任何道路直接相连。

输入以如下格式从标准输入给出。

第一行包含三个用半角空格分隔的整数，分别表示城市数 $N$（$1 \leq N \leq 100$）、道路数 $M$（$0 \leq M \leq N \times (N-1)/2$）以及目标组数 $K$（$1 \leq K \leq N$）。

接下来的 $M$ 行，每行包含三个用半角空格分隔的整数，分别表示一条道路连接的两个城市的编号 $f_i$、$t_i$ 以及分割该道路的代价 $c_i$。

对于每个 $i$，有 $1 \leq f_i \leq N$，$1 \leq t_i \leq N$，$f_i \neq t_i$，$1 \leq c_i \leq 1,000,000$。任意两个城市之间至多只有一条道路。某些城市可能没有任何道路相连。给定的图中至多只包含一个环。

输出一个整数，表示将城市分割为至少 $K$ 个独立组所需的最小代价。最后输出换行符。

• 有 $30$ 分的测试数据保证图中不包含环。
• 输入样例：

2 1 2
1 2 5

输出样例：

5

输入样例：

3 3 3
1 2 5
2 3 5
3 1 5

输出样例：

15

输入样例：

3 1 2
1 2 5

输出样例：

0

由 ChatGPT 4.1 翻译