Alice 喜欢旅游，在这个假期里他将沿着公路骑行。
可供 Alice 选择的道路构成了一张连通无向图，Alice 的起点位于1号点，终点位于n号点，每条道路有一个困难度 。定义一条路径的疲劳度为他路上经过的所有道路的困难度的最大值。
一开始 Alice 有k点体力，在通过一条道路时，他可以选择消耗若干点体力值，每消耗一点，道路的困难度也会降低 ，但一条道路的困难度不能低于 。
Alice 想知道他这次旅程的最小疲劳度。
Alice 喜欢旅游，在这个假期里他将沿着公路骑行。
可供 Alice 选择的道路构成了一张连通无向图，Alice 的起点位于1号点，终点位于n号点，每条道路有一个困难度 。定义一条路径的疲劳度为他路上经过的所有道路的困难度的最大值。
一开始 Alice 有k点体力，在通过一条道路时，他可以选择消耗若干点体力值，每消耗一点，道路的困难度也会降低 ，但一条道路的困难度不能低于 。
Alice 想知道他这次旅程的最小疲劳度。
第一行三个非负整数n,m,k，分别表示图的点数，边数以及 Alice 的初始体力值。
接下来m行，每行三个正整数 ，分别表示第i条边的两个端点以及困难度。
3 3 1
1 2 3
2 3 4
1 3 53
对于测试点 1、2 满足：n,m,k,vi<=1000。
对于测试点 3、4 满足：m=n-1。
对于测试点 5、6 满足：k=0。
对于所有测试点满足：2<=n<=50000,m,k,vi<=50000。