题目描述

$n$ 个城市，$m$ 条无向边，你要找 $t$ 条从城市 $1$ 到城市 $n$ 的路，使得最长的边的长度最小，每条边不能经过同一方向两次。也即一条边的两个方向各可以经过一次。

输入格式

第 $1$ 行三个整数 $n$，$m$，$t$ 用空格隔开。

第 $2$ 行到第 $m+1$ 行，每行包括三个整数 $u$，$v$，$w$ 表示城市 $u$ 到城市 $v$ 之间有一条长度为 $w$ 的道路。

输出格式

输出只有一行，包含一个整数，即经过的这些道路中最长的路的最小长度。

7 9 2
1 2 2
2 3 5
3 7 5
1 4 1
4 3 1
4 5 7
5 7 1
1 6 3
6 7 3

5

提示

数据规模与约定

对于 $100\%$ 的数据，保证：

• $2\le n\le200$，$1\le m\le 4\times 10^4$，$1\le t \le200$。
• $1 \leq u, v \leq n$，$1 \leq w \leq 2 \times 10^9$。
• 一定至少存在 $t$ 条从 $1$ 到 $n$ 的边集不相交的路径。