题目背景

EC-Final 比赛进行了四个小时，Jiangrc 学长的队伍虽然已经稳拿金牌，但三人均已饿得眼冒金星。Jiangrc 偷偷用手机点了一份极其豪华的“疯狂星期四”套餐。 外卖小哥到达了比赛场馆所在校园的大门（节点 $1$），而 Jiangrc 的队伍在赛场体育馆（节点 $N$）。 校园内部道路错综复杂，每条道路都有被保安抓包的风险值。幸运的是，Jiangrc 作为校园交际花，认识其中 $K$ 条道路上的保安，可以让他们“通融”一下，使得这 $K$ 条路上的风险值变为 $0$。

题目描述

校园可以看作一个包含 $N$ 个节点和 $P$ 条双向边（道路）的无向图，节点编号为 $1$ 到 $N$。每条边有一个风险值 $W_i$。 你需要帮外卖小哥规划一条从节点 $1$ 到节点 $N$ 的路径。你可以免费将路径上的最多 $K$ 条边的风险值变为 $0$。 这条路径的“总危险程度”定义为：路径上剩余的边中，风险值的最大值。（如果路径上的边数不超过 $K$，则总危险程度为 $0$）。 请你算出，如何规划路径并选择免费边，才能使得这条外卖路线的“总危险程度”最小？如果根本无法到达节点 $N$，输出 -1。

输入格式

第一行包含三个整数 $N, P, K$（$1 \le N \le 1000$, $1 \le P \le 10000$, $0 \le K \le 1000$）。 接下来 $P$ 行，每行三个整数 $A_i, B_i, W_i$（$1 \le A_i, B_i \le N$, $1 \le W_i \le 10^6$），表示连接 $A_i$ 和 $B_i$ 的双向道路，风险值为 $W_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 -> 3 -> 4 -> 5。风险值依次为 4, 7, 6。 由于 $K=1$，可以将风险值最大的边（3 -> 4，风险值 7）变为 0。 剩余边中风险值最大的是 1 -> 3 的 4 和 4 -> 5 的 6，等一下，如果免去 4 -> 5 的 6，或者免去 7，总危险程度为 4 吗？ 不对，最优路径是 1 -> 3 -> 2 -> 5，路径边权为 4, 3, 9。免掉权值为 9 的边，剩下最大边权为 4。