一张简单无重路图，有n个普通点可以使用加速通过，就是瞬间穿过他们移动到某点，有m个特殊点不能使用加速器通过，遇到要停下，编号是普通点1~n,特殊点是n+1~n+m，加速器每次只能加速通过不超过a的距离，加速器只能使用b次，使用时不耗时间瞬间移动，图中有c条边，为双向。从最后一个点走到第一个点。

第一行 一个整数T T<=10
每个测试样例包括
n m c a b
接下来是c行表示边的情况 u v w 表示u到v耗时w个单位时间

最短耗时

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

9