题目描述

WJJ喜欢旅游，这次她打算去一个据说有很多漂亮瀑布的山谷玩。
WJJ事先得到了一张地图，上面标注了N(1< = N< = 50)个小动物的聚居地，也就是一个个的小村落。其中第1个村
庄是WJJ现在住的地方，第N个村庄是WJJ打算去的地方。这些村庄之间有M(1< = M< = 150)条双向道路连接着，第j
条双向道路恰好直接连接两个小村庄A，B，长度为C(1< = A，B < = N，Ai<>B, 1< = C< = 1000)。道路有的是隧
道，有的是栈桥，地图上那些看起来在村庄之外交叉的路实际上并不相交——也就是说，如果把这些小村落和双向
道路构成的道路网看作图论意义上的图，我们不保证它是平面图，也不保证它没有重边。不过，有一点还是可以保
证的：WJJ细心地验证过，从它居住的村落一定能走到她想去的那个山谷。
在WJJ所在的神奇世界中，每只小动物都可以借助仙人掌来施放魔法，其中之一是，交换世界中任意两条双向道路
的长度，同时保持其他道路的长度不变。按WJJ目前的魔法水平，她最多能使用K(1< = K< = 20)次这种道路长度交
换魔法。可惜的是，由于仙人掌刺比较多，WJJ并不打算带着它旅行，于是她会在家里完成想要的道路交换后再出
门。假设WJI的旅行途中不会有其他小动物进行道路交换来破坏她设计好的路线。为了尽快达到目的地，WJJ希望她
需要走的总距离越短越好。也就是说，使用最多K次魔法后，从村落1到村落N的最短距离是多少？

输入格式

第1行：3个用空格隔开的整数N，M，K
第2．．M+1行：每行是3个整数，用空格隔开，分别表示A，B C

输出格式

1个整数，表示使用最多K次魔法后，村落1和村落N之间的最短距离。

样例输入

5  5  2
1  2  10
2  5  10
1  3  4
3  4  2
4  5  1

样例输出

3
一个可行的方案是，对调第1条边和第4条边的长度，再对调第1条边和第5条边的长度。对调后的最短路径为1-->2-
->5，长度为3。显然没有比这更优的方案了。

提示