背景 Background

在这个盛大的party上，由于太多朋友的缘故，candy给每一个人划分了一个地区，飘飘乎居士的地区是1，candy的地区是n。

描述 Description

聚会上一共有n个地区，编号从1到n（1<=n<=1000）。经过飘飘乎居士的计算共有p（0<p<=10000）对地区之间有一条相互连通的道路。飘飘乎居士将从1出发，目的地是n(也就是candy所在的地方)。他可以在2个相邻地区里行走，所耗费的体力为li。当然，飘飘乎居士为了能够尽快到达candy所在的地方，途中将会使用k(0<=k<=25)次飘飘神功，使用飘飘神功以后可以做到在2个相邻的地区行走不耗费任何的体力。 我们把整条线路中某2地耗费的最大体力值称为全程的代价。问题也就是求解最小代价是多少？

输入格式 Input Format

第一行，三个整数n p k

接下来p行，每行3个整数ai bi li（数据保证ai与bi之间只有一条道路相连），表示编号为ai与bi的地区之间有一条道路（道路是双向的），并且如果飘飘乎居士选择通过这条道路，那么他将消耗li的体力值。

输出格式 Output Format

一行，表示飘飘乎居士消耗的最小体力值是多少？如果不能到达，则输出-1

样例输入 Sample Input

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

样例输出 Sample Output

4

注释 Hint

一共5个地区，飘飘乎居士将从1出发，目的地是n。飘飘乎居士选择的路线如下1 —>3 ,3 —> 2 ,2 —> 5，经过这3个路线，耗费的体力分别为4 3 9，但是耗费体力最多的那个9，飘飘乎居士会使用飘飘神节省体力，因此，整个线路中耗费体力最多的道路变成了4，这样，代价变成了4。也就是最后的答案了。

来源 Source

来源 飘飘乎居士——Violet Hill