#4681. [Jsoi2010]旅行

内存限制:256 MiB 时间限制:30 Sec

题目描述

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。显然没有比这更优的方案了。

数据范围与提示