AT_joisc2010_finals.本選会場 (Finals)

JOI 全国有 $N$ 个城市，编号从 $1$ 到 $N$，还有 $M$ 条道路。

它连接两个不同的城市，并且是双向的。JOI 国家的任何两个城市之间都可以沿着公路从一个城市到达另一个城市。 JOI 国家的所有道路都是收费的公路，每条道路的通行费都是固定的。

JOI 信息奥林匹克竞赛也将在该国举行。JOI 需决定哪些城市举办决赛，并估算在这些城市举办所需的资金。

决赛将在 $K$ 个城市中举办，所有选手必须在决赛时转移到其中一个城市。 在一个城市可以聚集的选手数量没有限制。

每个选手到决赛的城市时都会经过一条道路。 每条道路都会收每个选手 $C$ 元钱。

因此，通过设计选手移动的顺序，可以通过允许多个选手同时通过来节省费用。我们希望决定决赛将在哪个城市举行，并尽量减少在最终选拔场地聚集选手时产生的通行费总和。

给定有关 $N、M、K$ 以及所有道路的信息，计算在决赛中聚集选手所需的最低通行费总和。

• 第一行输入三个整数 $N、M、K$。

• 在第 $2$ 至 $M+1$ 行中，每行输入三个整数 $A_i，B_i，C_i$，表示道路 $i$ 的情况。

输出一个整数，表示在决赛中聚集选手所需的最低金额。

对于 $40\%$ 的数据，$N=1000，K=1$。

对于 $20\%$ 的数据，同时满足这两个条件。

对于 $60\%$ 的数据，至少满足这两个条件之一。

对于 $100\%$ 的数据，$1 \le N \le 100000，1 \le M \le 100000，1 \le K \le N，1 \le A_i<B_i \le N，1 \le C_i \le 100$。

输入输出样例

输入示例#1

4 3 1
1 2 2
2 3 9
2 4 5

输出示例#1

16

样例1解释

例如，假设最后一轮在城市 $1$ 举行，城市 $4$ 的选手将首先移动到城市 $2$，然后是城市 $3$ 的代表将选手移动到城市 $2$，并将城市 $2$ 中的三个选手移动到城市 $1$。

输入示例#2

5 6 2
1 2 5
1 3 3
2 3 4
2 5 7 
3 4 6
4 5 5

输出示例#2

12

样例2解释

如果决赛在 $3$ 市和 $4$ 市举行，则 $1$ 市和 $2$ 的选手应聚集在城市 $3$，城市 $5$ 的选手应聚集在城市 $4$。