危险的游戏

Time Limit: 5000 ms

Memory Limit: 655350 ms

Description

话说ZLLY的GF非常的刁难,经常对ZLLY做一个忠诚度的测试,比如,有一项就是让ZLLY去买可爱多,而且时间由她来决定,一旦超过她规定的时间,则今天剩下的时间就不理ZLLY了。这让ZLLY非常的痛苦,现在请你帮助下ZLLY,给他指出一条最短的路径,让他在最短的时间内完成GF的测试。

Input

第一个数是整数n(n<=50),表示有n组数据。 每组数据第一行是m(m<=5000),k(k<=m*(m-1)),v,t表示有m(位置编号从1到m)个位置,k条路,v是ZLLY的速度,t是ZLLY的GF要求达到的时间(保留到小数点后2位)。 接着是k组数据,每组数据有三个数a,b,c表示a可以到达b点,路程是c。 然后是两个数s和e,表示ZLLY现在所在的位置和有可爱多卖的位置.

Output

输出从ZLLY所在位置到卖可爱多位置的最短时间 如果不能买到的话(没有路到达)后时间输出ZLLY will cry!

Sample Input

2
4 5 1.00 10.00
1 2 2
1 3 4
2 3 3
2 4 2
3 4 3
1 4
4 3 1.00 5.00
1 2 2
1 3 2
2 3 4
1 4

Sample Output

4.00
ZLLY will cry!

Hint

Source

dreaming3000

提交代码