题目描述

光头强想在他的农场里架设一条电话线。不幸的是，天下没有免费的午餐，因此他需要支付将农场连接到电话系统所需的一些电缆费用。

有 $N$ 个废弃电话杆，编号为 $1\dots N$，分布在光头强的农场周围，但没有电缆连接它们。总共有 $P$ 对电杆可以用电缆连接，其余的相距太远无法直接连接。

第 $i$ 对可以连接的两个不同的电话杆为 $A_i$ 和 $B_i$，所需电缆长度为 $L_i$单位。输入数据不包含重复的 $\{A_i,B_i\}$ 对。电话杆 $1$ 已经连接到电话系统，电话杆 $N$ 在农场。电话杆 $1$ 和 $N$ 需要通过电缆路径连通；其余的杆可以使用或不使用。

电话公司愿意免费为光头强提供 $K$ 条电缆用以连接 $K$ 对电话杆。除此之外，他将不得不支付与他所需的其余电缆中最长一根的长度相等的费用（每对电线杆都用一根单独的电缆连接），如果他不需要任何额外的电缆，则为 $0$。

确定光头强必须支付的最低金额。

输入描述

第一行包含三个整数 $N,P,K$，分别表示电话杆数量、可以连线的电话杆对数，可以免费连接的对数。

接下来 $P$ 行每行 $3$ 个整数 $A_i,B_i,L_i$ ，分别表示可以连接的电话杆对，以及需要的电缆长度。

输出描述

输出一个整数表示答案。如果无法连通，输出 $-1$。

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

4

评测用例规模与约定：

$1≤N≤1000，1≤P≤10000，1≤L_i≤10^6，0≤K<N$。