题目描述
在拯救了美丽的公主之后，超级马里奥需要找到回家的路——当然了，是和公主一起。马里奥对“超级马里奥世界”非常熟悉，因此他不需要地图，他只需要一条最佳路径来节省时间。
在超级马里奥世界中，总共有 $A$ 座村庄和 $B$ 座城堡。村庄编号从 $1$ 到 $A$，城堡编号从 $A + 1$ 到 $A + B$。马里奥居住在村庄 $1$，他需要从城堡 $A + B$ 出发返回村庄 $1$。在不同的两个地点之间有双向道路连接，两个地点最多只有一条道路连接，而且不会出现一条道路的两端连接同一处地点的情况。马里奥已经测量了每条道路的长度，但是他并不想一直走路回家，因为每走一单位的距离就要花费他一单位的时间。
幸运地是，在拯救公主的城堡中，马里奥发现了一双魔法鞋，如果穿上它们，他就能够从一个地方瞬移到另外一个地方，而且不用花费任何时间。（不用担心公主，马里奥已经找到一种安全的方法带着公主和他一起瞬移，但他是不会告诉你究竟是如何做到的）
由于城堡中存在陷阱，马里奥在瞬移过程中不会径直穿过某个城堡。如果有城堡在瞬移的路径中，他会在到达城堡时停下来，结束此次瞬移。而且，马里奥总是在村庄或者城堡时开始瞬移或者停止瞬移，而不会在两个地点连接的道路中途停止瞬移。不过，由于魔法鞋太旧了，马里奥使用魔法鞋一次最多只能瞬移 $L$ 千米的距离，而且使用魔法鞋的次数总共不能超过 $K$ 次。

输入格式
本题有多组数据。
输入的第一行包含一个整数 $T$，表示测试数据的组数 $(1 \leq T \leq 20)$。每组测试数据的第一行包含 $5$ 个整数：$A, B, M, L, K$。$A$ 表示村庄的数量，$B$ 表示城堡的数量 $(1 \leq A, B \leq 50)$。M表示道路的数量，$L$ 表示一次瞬移所能经过的最长距离 $(1 \leq L \leq 500)$，$K$ 表示魔法鞋能够使用的次数 $(0 \leq K \leq 10)$。紧接着的 $M$ 行，每行包含三个整数 $X_i, Y_i, L_i$，表示有一条道路连接地点 $X_i$ 和 $Y_i$，它们之间的距离是 $L_i$，走完该道路的时间也是 $L_i(1 \leq L_i \leq 100)$。

输出格式
对于每组测试数据输出一行，此行包含一个整数，表示马里奥和公主回家所需花费的最少时间。你可以假定，对于所有测试数据，马里奥总是能够找到回家的路。