問題
N 。当将城市分解为 K 个以上的独立组时,请求出分解所需的最小成本。在此,某个 2 个组是独立的,意味着各组之间的城市没有道路相连。
入力
N M K
f_{1} t_{1} c_{1}
f_{2} t_{2} c_{2}
...
f_{M} t_{M} c_{M}
- 1 行表示城市的数量 N(1 ≦ N ≦ 100)和道路的数量 M(0 ≦ M ≦ N*(N-1)/2)),以及目标的组数 K(1 ≦ K ≦ N) 由半角空格分隔。 您可以假设
- 2 行目~ M+1 行包含每条道路的信息,即道路连接的两个城市编号 f_{i} 和 按字典顺序比较 t_{i},以及分割成本 c_{i} 由半角空格分隔。 关于
- 各 i 关于 1 ≦ f_{i} ≦ N 和 1 ≦ t_{i} ≦ N , f_{i} ≠ t_{i} , 1 ≦ c_{i} ≦ 1,000,000 很满意。
- 2 连接城市的道路数最多为 1 条道路。城市可能没有任何道路。 1 也可能没有道路。
- 给定图中包含的回路数最多为 1 这是一个。
出力
请在末尾输出换行符。
部分点
入力例 1
2 1 2 1 2 5
出力例 1
5
入力例 2
3 3 3 1 2 5 2 3 5 3 1 5
出力例 2
15
入力例 3
3 1 2 1 2 5
出力例 3
0