Farmer John 想在农场安装电话线。不幸的是，电话公司不愿配合，所以他需要支付将农场接入电话系统所需的部分电缆费用。

Farmer John 的地里散落着 $N$ 根孤零零的电话杆，$(1 \le N \le 1,000)$，方便起见编号为 $1..N$；目前它们之间没有任何电缆连接。共有 $P$ 对电话杆（$(1 \le P \le 10,000)$）可以用电缆相连，其他电话杆对距离太远。

第 $i$ 根电缆可以连接两根不同的电话杆 $A_i$ 与 $B_i$，使用时长度为 $L_i$ 单位，$(1 \le L_i \le 1,000,000)$。输入数据不会将任意一对 {$A_i,B_i$} 给出超过一次。电话杆 $1$ 已经接入电话系统，电话杆 $N$ 位于农场。需要用一条电缆路径连接电话杆 $1$ 与 $N$；其他电话杆可以使用，也可以不使用。

事实上，电话公司愿意免费提供 $K$ 根电缆给 Farmer John，$(0 \le K < N)$。除此之外，他必须支付的费用等于所需其余电缆中最长一根的长度（每对电话杆用一根独立电缆相连）；如果不需要额外电缆，则费用为 $0$。

确定 Farmer John 必须支付的最少金额。

输入格式

从标准输入读取输入。

• 第 1 行：三个用空格分隔的整数：$N$、$P$ 和 $K$。

• 第 $2..P+1$ 行：第 $i+1$ 行包含三个用空格分隔的整数：$A_i$、$B_i$ 和 $L_i$。

输出格式

将输出写入标准输出。

• 第 1 行：一个整数，表示 Farmer John 可以支付的最少金额。如果无法将农场连接到电话公司，输出 $-1$。

样例

输入格式 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

输出格式 1

4

说明

有 5 根电话杆。电话杆 $1$ 不能直接连接电话杆 $4$ 或 $5$。电话杆 $5$ 不能直接连接电话杆 $1$ 或 $3$。其余所有电话杆对都可以连接。电话公司会提供一根免费电缆。

若把电话杆 $1$ 连到 $3$，$3$ 连到 $2$，$2$ 连到 $5$，Farmer John 便需要长度为 $4$、$3$ 和 $9$ 的电缆。电话公司会提供长度为 $9$ 的电缆，所以剩余所需电缆中最长的长度为 $4$。

题目作者：Paul Christiano，2007