该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

写在前面

或许前路永夜，即便如此我也要前进，因为星光即使微弱也会为我照亮前路。

——宫园薰 《四月是你的谎言》

当您看到这道题的时候，说明您离AK只有最后一题之遥了。

祝每一位努力的人都会取得好成绩！

PS：题目讲解会将全部的题目梗都说出来

题目背景

“真的就这样离开了吗…...”

初中马上就要毕业了，wyh只能看着自己的同学们渐行渐远。

"你...真的就要这样走了？"一位同学W的声音响起。

"不。"

原来，还有同学能和自己在一个高中啊…...

题目描述

现在有N个社区，有M条道路连接，W现在即将离开，前往一中北校区参加新生报道。

wyh住在1号小区，而W住在N小区。

wyh想和（他？她？它？）一起去报道，但是wyh清楚的知道，现在去已经赶不上了。

突然，wyh打开了手机，发现自己的手机上多了一本红色的书，上面只印了一句话。

现在知道，每当wyh念这句话的时候，周围人的时间都会减缓50%，也就是说，在通过一条马路时，wyh可以通过念诗来使通过这条路径的时间减少50%。这样就有可能追上W了。

对了还有，如果wyh念诗的数量超过K，就会被热心的水表员识别并清除，毕竟控制时间的力量不是一般人能掌握的，再说了，W同学也不想看到那热心过度的水表员。所以说，wyh要在用时最短的前提下，尽量使得念诗的次数最少。

那么，一切就开始了…...

输入格式

第一行包含三个整数：N、M、K。

接下来 M 行，每行包含三个整数：\(U_i\)、\(V_i\)、\(T_i\)，表示存在一条 \(U_i\)与 \(V_i\)之 间的双向道路，在不念诗的前提下，通过它需要 \(T_i\)的时间。

最后一行包括一个整数W，表示同学W准备出发的时间

输出格式

输出包括两行

第一行表示wyh能不能追上W，如果能，输出YES否则输出QaQ

第二行表示wyh到达用的时间.输出对\(10^7 + 9\)取模。

样例输入

4 4 1
1 2 4
4 2 6
1 3 8
3 4 8
10

样例输出

YES
7

数据范围&时间限制

所有的数据一律128M

前95%的数据为0.5s

后5%的数据为1s

对于10%的数据，保证K = 0

对于另外20%的数据，保证K = 1

对于另外20%的数据，保证K <= 3，M <= 200

对于95%的数据,保证1  ≤  K  ≤  N ≤  50 ，M  ≤  1000，1≤  U_i，V_i ≤  N，1 ≤  T_i  ≤  2000，T_i &1 = 0

对于最后5%的数据 保证\(N <= 5005,M <= 125005\)

所有数据中的无向图保证无自环、重边，且是连通的。

请注意常数因子可能会带来的影响