时间限制： 1.0 秒

空间限制： 256 MB

题目描述

巨大的海域上分布着 $n$ 个小岛，这些小岛由 $m$ 座桥梁连接，每座桥梁连接两个小岛，所有桥梁都是双向通行的。这些桥梁能承受的重量都是有限的，不同桥梁承重可能不同。我们说一个桥梁的承重能力为 $w$，如果一辆车可以运输重量为 $w$ 的货物安全通过该桥梁，但是不能再多运一点点货物。

现在 R 公司要在海域上的某个小岛建立一个仓库，公司希望仓库的货物可以运往至少 $k$ 个小岛（包括建立仓库的小岛）。求在上述条件下，每车货物的最大重量。

输入格式

从标准输入读入数据。

第一行包含三个整数 $n, m, k$。

接下来 $m$ 行，其中的第 $i$ 行包括三个整数 $u_i, v_i, w_i$。表示小岛 $u_i$ 和小岛 $v_i$ 之间有一座承重为 $w_i$ 的桥梁。

输出格式

输出到标准输出。

输出一行，仅包括一个整数，表示每车货物的最大重量。若无论每车货物的重量为多少都无法使得货物可以运往至少 $k$ 个小岛，则输出 $0$。

5 7 3
1 2 10
2 3 3
1 4 3
3 4 6
3 5 5
4 5 7
1 1 22

6

样例 1 解释

将仓库建在第 $5$ 个小岛，重量为 $6$ 的货物可以运往 $3,4,5$ 这三个小岛。

子任务

对于 $40\%$ 的数据，有 $2 \le k \le n \le 10^3,~1 \le m \le 5 \times 10^3$。

对于 $100\%$ 的数据，有 $2 \le k \le n \le 10^5,~1 \le m \le 5 \times 10^5,~1 \le w_i \le 10^6$。