题目描述

焦作一中的机房遭受总创，所有网线失效。机房中共 n 台计算机，标号为 1~n，它们之间任意两台计算机都没有连接。并且，不是任意两台计算机都可以被修复连接，只有其中 p 对电脑之间是可以用网线互相连接的，且网线长度不同。

现在需要恢复焦作一中机房网络，目标是使第 n 台机器能直接或间接地和 1 号计算机通信。

显然有多种修复连线方案完成修复目标，然而焦作一中还是希望能花费尽可能少的代价完成修复。

保险公司可以为焦作一中报销修复过程中 k 对计算机之间的网线费用，其余的网线费用则需要焦作一中 自己负责。修复一条网线所需要的费用为该网线长度。

请计算在能达成修复目标的情况下，焦作一中自己修复的网线中最长的那根线路长度最短可以是多少。

输入格式

输入包括 p + 1 行。

第一行三个整数 n, p, k。

接下来 p 行，每行包含三个整数 a, b, t，表示有一条网线可以连接 a号计算机和 b 号计算机，网线长度为 t。

输出格式

输出包括 1 行。

第一行是一个数字，代表最小花费。如果无法完成目标，则输出-1。

样例数据

input

5 7 1

1 2 5

3 1 4

2 4 8

3 2 3

5 2 9

3 4 7

4 5 6

output

4

数据规模与约定

对于 30%的数据：k<=n<=10, p<=50；

对于 60%的数据：k<=n<=500, p<=1000；

对于 100%的数据：k<=n<=1000, p<=10000。任意两根网线长度相加在 int 范围内。

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$