说明

徐老师刚新建了一栋别墅，现在他要架设电线给别墅通电。

供电所的编号为 1，徐老师的别墅编号为 N，中间有 N-2 根电线杆，编号依次为 2 ...... N - 1。徐老师对于电量需求很大，需要通过电线杆架设私有电网。由于原先已经架设了很多电线，出于安全考虑，现在只有 P 对电线杆之间能架设电线（我们把供电所和别墅也当成一个电线杆），每一对包含两个电线杆 A_i 和 B_i，在 A_i 和 B_i 之间架设电线需要 L_i 米电线。

现在需要假设电线让供电所和徐老师的别墅能通电。徐老师依靠其强大的个人魅力，争取到让供电所免费帮他在 K 对电线杆直接架设电线，而剩下部分需要收费，收费标准为剩下的需要架设的电线的长度的最大长度。

帮忙计算一下，徐老师最少需要多少钱来架设电线。

输入格式

第一行输入 3 个整数 N(2 <= N <= 1000)，P(1 <= P <= 10000)，K(0 <= K < N)。

接下来输入 P 行，每行 3 个整数 A_i, B_i(1 <= A_i, B_i <= N)，L_i(1 <= L_i <= 10^6)，表示 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