描述

神犇zzy要出门旅游啦!!!
与其说是去旅游,不如说是去冒险。
在遥遥旅途中,zzy走到了A国,当然,他还要去到下一个国家B国,所谓环游世界嘛。
但是A国和B国之间是一片沙漠,并没有修建公路,而且zzy孤身独行,他为了显示大男子气概,决定一人独闯沙漠。
在独闯沙漠之前,zzy当然先要调查地形,据悉沙漠中有N个停靠站,分别编号为1…N,这些停靠站都建立在绿洲旁。特别的,1号停靠站就是A国的边境,zzy从1号停靠站出发;N号停靠站是B国的边境,zzy只要到达N号停靠站就认为他到达了B国。
zzy有一个方便携带的容积为V的背包,可以装纳体积之和不超过V的水和食物。zzy每走一单位的距离,他就要消耗一单位的水和一单位的食物,这是必须的。
由于停靠站建立在绿洲旁,zzy可以在停靠站上装任意多的水。
但是绿洲毕竟是绿洲,就没有什么食物了,所以想要食物就必须从A国买食物,再从1号停靠站进入沙漠,可以认为在1号停靠站可以得到任意多的食物。当然,zzy可以把食物存放在任意一个停靠站。
由于zzy孤身独行,当然了他的Money自然不紧缺,但是A国真是太XX了,连个ATM都没有,于是zzy只有手中剩下的一些钱币。
食物是要用钱币买的,在没办法的情况下,只能尽量的节约用钱,食用最少的食物。

输入格式

输入数据第一行是三个正整数N,M,V,分别表示停靠站的个数,停靠站之间的双向道路条数,以及zzy背包的容积。
接下来M行,每行包括三个正整数x,y,d,表示停靠站x与y之间存在一条长度为d的边。

输出格式

输出数据仅包含一行,输出最少食用的食物数量。题目保证zzy一定可以从A国到达B国。保证答案一定小于10^15。

样例输入

6 7 10
1 2 3
1 5 2
2 3 5
2 4 3
2 5 4
2 6 5
3 4 2

样例输出

14

数据范围与约定

方案是:
① 从A国出来,在1号停靠站处,背包装上7单位食物和3单位水;
② 走到2号停靠站,背包上剩下4单位食物和0单位水,这时把1单位食物留下,把6单位水放入背包;
③ 走回1号停靠站,背包上剩下0单位食物和3单位水,这时把7单位食物放入背包;
④ 走到2号停靠站,背包上剩下4单位食物和0单位水,这时把留在2号停靠站的1单位食物放入背包,再把5单位水放入背包;
⑤ 走到6号停靠站,背包上剩下0单位食物和0单位水,到达B国!
一共用了14单位食物。
而且没有更好的方案可以减少食物的使用量。

对于30%的数据,N<=10,M<=20,V<=20;
对于60%的数据,N<=50,M<=200,V<=200;
对于90%的数据,N<=1,000,M<=2,000,V<=10,000;
对于100%的数据,N<=10,000,M<=20,000,V<=1,000,000,任意道路的长度d<=1,000,000。
平均分布着30%的数据,满足M=N-1。