Description
遗迹中有N个祭坛，昆西位于1号祭坛，这N个祭坛通过M座魔法阵相连，每座魔法阵连通祭坛ui和祭坛vi(魔法阵是双向的)，但是每座魔法阵的开启需要一定的时间 ci，可爱的0v0作为战舰少女，有强大的魔法，因此她可以让k座魔法阵的启动时间缩短s（最短缩短到0），昆西想要尽快的到达T号祭坛，这样子她就可以叫航母来把她接走了，由于昆西实在是太爱学习了，所以她想让你帮她算一算，所需的到达T号祭坛的最短时间是多少，作为回报，他会给你一艘新奥尔良级别的同伴。另外，如果到达不了T号祭坛，请输出0v0
Input
第一行5个整数，N，M，T，k，s
接下来M行，每行3个整数，ui,vi,ci
Output
一行1个整数，表示到达T号祭坛最短的用时
如果到达不了T号祭坛，请输出0v0
4 5 4 2 10
1 2 5
1 3 7
2 3 3
2 4 6
1 4 10
HINT
对于30%的数据，保证N<= 1000 ; M <= 10000
其中10%的数据，保证k=0
对于100%的数据，保证N <= 10000 ; M <= 100000 ;k <=20 ;s <= 1000
T,u_i,v_i <= N;c_i<= 1000