24116번 - 本選会場 (Finals) 다국어

JOI 国には N 個の都市があり，1 から N の番号がついている．また，M 本の道路がある．全ての道路は 異なる 2 つの都市を結び，双方向に通行可能である．JOI 国の任意の 2 つの都市は，道路をたどって片方か らもう片方へ到達可能である．JOI 国の道路は全て有料道路であり，道路ごとに通行料金が決まっている．

JOI 国でも情報オリンピックは開催される．JOI 国の情報オリンピックの本選には，各都市の代表選手が 出場する．本選をどの都市で開催するかを決定し，選手をそれらの都市に集めるためにかかる金額を見積 もっておく必要がある．本選は K 個の都市で開催し，本選の際には全ての選手をそれらのいずれかの都市 に移動させなければならない．1 つの都市に集まる選手の人数に制限はない．

本選を開催する都市に選手を集める際には，道路を利用する．通行料金が c の道路は，一度に何人で通 行しても料金は c である．そこで，選手を移動させる順番を工夫することによって，複数の選手を一度に 通行させるようにすれば，料金を節約することができる．

本選を開催する都市を決定し，選手を本選会場に集める際にかかる通行料金の和を最小化したい．

N, M, K と全ての道路の情報が与えられたとき，選手を本選会場に集める際にかかる通行料金の和の最小 値を計算するプログラムを作成せよ．

標準入力から以下の入力を読み込め．

• 1 行目には整数 N, M, K が空白を区切りとして書かれている．
• 続く M 行には，1 行につき 1 つの道路について記述されている．これらの行のうちの i 行目は道路 i について記述しており，整数 A_i, B_i ,C_i が空白を区切りとして書かれている．

標準出力に選手を本選会場に集める際にかかる金額の最小値を表す 1 つの整数を出力せよ．

• 1 ≤ N ≤ 100, 000 都市の数
• 1 ≤ M ≤ 100, 000 道路の数
• 1 ≤ K ≤ N 本選を開催する都市の個数
• 1 ≤ A_i < B_i ≤ N 道路 i の結ぶ 2 つの都市
• 1 ≤ C_i ≤ 100 道路 i の通行料金