测试数据来自 system/2048

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

哪吒闹海之回家

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　再次成功营救出敖丙后，哪吒要从太乙真人的城堡中返回他的家。哪吒的世界里一共有 \(N\) 个村庄和 \(M\) 个城堡，其中村庄编号为 \(1 \sim N\)，城堡编号为 \(N+1 \sim N+M\)。哪吒的家在村庄1，而太乙真人住在城堡 \(N+M\)。

　　哪吒能以1千米每秒的速度沿着村庄和城堡之间的双向道路行走，也可以用风火轮加速。风火轮可以让哪吒瞬间移动不超过 \(X\) 千米，但由于城堡中有很多陷阱，稍不留神就会中圈套，因此哪吒从不使用风火轮穿过城堡（除起点和终点外，中途不能经过城堡）。另外，使用风火轮的起点和终点只能是城堡或者村庄，且最多使用 \(K\) 次。

　　你的任务是计算哪吒回家的最短时间。输入数据保证他一定能回家。

【输入格式】

　　第一行为整数 \(N, M, P, X\) 和 \(K\)，分别表示村庄，城市数目，道路数量，风火轮的最远行程和最多能使用风火轮的次数。
　　接下来的 \(M\) 行，每行表示一条道路 \(a_i,b_i,d_i\)，分别表示一条双向道路的两个端点和长度。

【输出格式】

　　一个整数，表示哪吒回家的最短时间。

【输入输出样例】

　Input

4 2 6 9 1
4 6 1
5 6 10
4 5 5
3 5 4
2 3 4
1 2 3

　Output

9

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N+M≤500\)，\(1≤X≤500\)，\(1≤K≤10\)，\(1≤d_i≤100\)。

【来源】

　　Mr.he