T2--骑行(1s/512M)

题目描述

Alice 喜欢旅游，在这个假期里他将沿着公路骑行。

可供 Alice 选择的道路构成了一张连通无向图，Alice 的起点位于 $1$ 号点，终点位于 $n$ 号点，每条道路有一个困难度 $v_i$。定义一条路径的疲劳度为他路上经过的所有道路的困难度的最大值。

一开始 Alice 有 $k$ 点体力，在通过一条道路时，他可以选择消耗若干点体力值，每消耗一点，道路的困难度也会降低 $1$，但一条道路的困难度不能低于 $0$。

Alice 想知道他这次旅程的最小疲劳度。

输入格式

第一行三个非负整数 $n, m, k$，分别表示图的点数，边数以及 Alice 的初始体力值。

接下来 $m$ 行，每行三个正整数 $x_i, y_i, v_i$，分别表示第 $i$ 条边的两个端点以及困难度。

输出格式

输出一个整数， 表示答案。

样例

见 down/ride 目录下的样例文件。

数据范围

对于测试点 1、2 满足：$n,m,k,v_i \le 1000$。

对于测试点 3、4 满足：$m = n-1$。

对于测试点 5、6 满足：$k=0$。

对于所有测试点满足：$2 \le n \le 50000,m, k, v_i \le 50000$。