题目背景

B 地区在地震过后，所有公路都造成了一定的损毁，而这场地震却没对村庄造成什么影响。当地部门正在对公路进行重建。

题目描述

B 地区共有 $N$ 个村庄，编号从 $1$ 到 $N$。有 $M$ 条双向通行的公路需要重建。每条公路都连接两个不同的村庄，两个不同的村庄之间最多有一条公路。（无自环，无重边）

现在，小 A 作为重建公路的负责人，接到了一项紧急任务，当务之急是：先修建一些公路，使得从村庄 1 可以到达村庄 N。这样，有些公路可以暂缓修建。为了完成这项紧急任务，财政部门决定拨款专项资金，用于 K 条公路的修建。至于哪 K 条公路，小 A 可以任意指定，这些被指定的公路的修建费用将由财政部门全额补贴。对于剩余亟需修建的公路，则需要小 A 自行出资，费用金额为：在亟需修建的公路中，长度最长的那条公路的长度。当然，如果亟需修建的公路数目不超过 K 条，小 A 就无需自掏腰包了。

小 A 自然想节约资金。那么如何设计施工方案，可以保证完成紧急任务，且使得自行出资的费用最小呢？

你能帮助他吗？你只需要输出小 A 需要自行出资的最小费用。

输入格式

第一行包含三个整数 $N, M, K$，依次表示村庄的数目、公路的数目以及财政部门出资的公路数目。

接下来 $M$ 行，每行 $3$ 个整数 $u,v,w$，表示有一条连接村庄 $u$ 与村庄 $v$ 的公路，长度为 $w$，保证 $u \neq v$，且对于任意一对村庄只会存在一条公路。

输出格式

一个整数，表示小 A 需要自行出资的最小费用；如果无法完成任务则输出 -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

数据范围

100% 的数据： $1 ≤ N ≤ 1000$，$1 ≤ M ≤ 10000$ ，$1 ≤ u, v ≤ N$，$1 ≤ w ≤ 10^6$， $0 ≤ K ≤ M$