E - 独立記念日 Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB

　長らく続いたW帝国がその歴史に終止符を打とうとしていた．多くの少数部族の反乱により，複数の独立国家に分かれることになったのだ．そこで，帝国のとある領主は次のやっかいな問題に直面している．彼の最後の仕事を手伝ってあげよう．

問題

　N 個の都市を繋ぐ M 個の道路の情報が与えられる．各道路は異なる 2 つの都市を繋いでおり，双方向に移動することができる．道路の情報は2つの異なる都市の番号(1 ～ N)と分断コストで与えられる．なお，2 つの都市を結ぶ道路の数は高々 1 つであり，閉路の数も高々 1 つである．

　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 行に出力せよ．
なお、最後には改行を出力せよ．

部分点

30 点分については，グラフに閉路を含まないことが保証される．

入力例 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 つのグループに分けるためには，すべての道路を切断する必要があり，それには 5 + 5 + 5 = 15 のコストがかかる．

入力例 3

3 1 2
1 2 5

出力例 3

0
既に 2 つのグループ(\{1,2\} と \{3\})に分かれているため，これ以上道路を切断する必要はない．よって，0 を出力する．