题目描述
通信网络有 $n$ 个节点、$p$ 条双向缆线（各有升级价）。要连通节点 $1$ 与节点 $n$， 可以指定一条路径，并豁免路径上至多 $k$ 条缆线的费用，只需支付路径上剩余缆线中 最贵的那条的价钱。求最小支付；若 1 与 n 不连通，输出 $-1$。
输入格式
第一行三个整数 $n, p, k$； 接下来 $p$ 行，每行三个整数 $u, v, w$，为一条缆线的两端与升级价。
输出格式
一行一个整数：最小支付，不连通输出 $-1$。
数据范围
$$1 \le n, p \le 5000$$
，$$0 \le w_i \le 10^6$$
，$$0 \le k \le p$$
。