题目内容

路径的瓶颈带宽是这条路上所有链路带宽的最小值。例如城市 $0$ 到 $1$ 的带宽为 $8\,Gb/s$，城市 $1$ 到 $2$ 的带宽为 $16\,Gb/s$，则这条路的瓶颈带宽是 $8\,Gb/s$。

作为智慧城市项目组的工程师，你要优化城市之间的数据网络。现有 $c$ 个城市（编号从 $0$ 到 $c-1$）和 $d$ 条双向数据链路，每条链路有一个传输带宽（单位：$Gb/s$）。

预算只允许你选定一条从城市 $0$ 到城市 $c-1$ 的路径，并把这条路径上恰好 $t$ 条现有链路升级：升级后该链路带宽变为原来的 $2$ 倍，且每条链路最多升级 $1$ 次。你也可以整条路径都不升级。若某条路径上的链路数不足 $t$，则这条路径不能执行升级。

请计算升级方案确定之后，所有可行路径里能得到的最大瓶颈带宽。

注意：

• 每条链路最多升级 $1$ 次
• 若需要升级，必须恰好升级 $t$ 条，不能多也不能少
• 如果城市 $0$ 无法到达城市 $c-1$，输出 $-1$

约束条件

• $2 \le c \le 100$
• $1 \le d \le 1000$
• $0 \le t \le \min(10,d)$
• $1 \le b \le 999$

输入描述

第一行三个整数 $c$、$d$、$t$，依次表示城市数量、链路数量和升级条数。

接下来 $d$ 行，每行三个整数 $x$、$y$、$b$，表示城市 $x$ 与城市 $y$ 之间有一条带宽为 $b$ 的双向链路。

输出描述

输出一个整数，即最大瓶颈带宽；若城市 $0$ 无法到达城市 $c-1$，输出 $-1$。

样例1

输入

3 1 0
0 1 7

输出

-1

说明

只有城市 $0$ 与 $1$ 相连，无法到达城市 $2$。

样例2

输入

5 6 2
0 1 11
0 2 16
1 2 4
1 3 22
2 4 14
3 4 19

输出

28

说明

选择路径 $0 \rightarrow 2 \rightarrow 4$，把 $(0,2)$ 和 $(2,4)$ 都升级，带宽变为 $32$ 和 $28$，瓶颈带宽为 $28$。

样例3

输入

6 8 2
0 1 9
1 5 9
0 2 14
2 3 14
3 5 14
0 5 36
2 4 7
4 5 7

输出

36

说明

直连 $0 \rightarrow 5$ 只有一条链路，不能恰好升级 $2$ 次，因此只能按原带宽 $36$ 使用。其它路径升级后瓶颈仍不超过 $36$，所以答案是 $36$。