题目内容

某智慧城市项目需要优化一个由 $c$ 个城市和 $d$ 条双向数据链路组成的通信网络。城市编号为 0 到 $c-1$，每条链路连接两个不同城市，并具有一个传输带宽，单位为 $Gb/s$。

对于从城市 0 到城市 c-1 的一条路径，其瓶颈带宽定义为该路径上所有链路带宽的最小值。瓶颈带宽决定了整条路径的实际传输能力。

现在需要从城市 0 到城市 c-1 选择一条路径。工程预算支持对路径上的链路进行升级，但只能采用以下两种方案之一：

• 不升级该路径上的任何链路；
• 在该路径上选择恰好 $t$ 条链路进行升级。

每条被升级的链路带宽变为原来的 2 倍，并且每条链路最多只能升级一次。如果一条路径包含的链路数量少于 $t$，则该路径不能采用第二种升级方案。

请计算在所有可行路径以及对应升级方案中，能够得到的最大瓶颈带宽。如果城市 0 无法到达城市 c-1，则结果应输出 -1。

约束条件

• 城市数量 $c$ 的范围为 2 到 100。
• 链路数量 $d$ 的范围为 1 到 1000。
• 升级条数 $t$ 至少为 0，且不超过 10，同时不超过链路数量 $d$。
• 每条链路带宽 $b$ 的范围为 1 到 999。

输入描述

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

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

输出描述

输出一个整数，表示能够得到的最大瓶颈带宽。如果城市 0 无法到达城市 $c-1$，则输出 -1。

样例1

输入

2 1 0
0 1 5

输出

5

说明

城市 0 到城市 1 只有一条带宽为 5 的链路。因为 $t=0$，不能升级链路，路径瓶颈带宽就是该链路的带宽 5。因此最大瓶颈带宽为 5。

样例2

输入

4 4 1
0 1 3
1 3 4
0 2 5
2 3 2

输出

4

说明

选择路径 0 -> 1 -> 3，升级0 -> 1的带宽为 3 的链路，升级后该路径链路带宽为 6、4，瓶颈带宽为 4。

因此最大瓶颈带宽为 4。

样例3

输入

5 4 2
0 1 8
1 2 2
2 3 9
3 4 3

输出

4

说明

选择路径 0 -> 1 -> 2 -> 3 -> 4，升级带宽为 2 和 3 的两条链路，升级后路径链路带宽为 8、4、9、6，瓶颈带宽为 4。

因此最大瓶颈带宽为 4。

样例4

输入

4 2 1
0 1 5
2 3 7

输出

-1

说明

城市 0 只与城市 1 相连，城市 2 只与城市 3 相连，图中没有连接两个连通块的链路。因此从城市 0 无法到达城市 3，输出 -1。