//最短路：Floyd+SPFA(BFS)+DP

 //Time:20Ms    Memory:336K

 //题目很好，数据较弱，网上部分代码有些问题却能够A掉

 //题意：超级马里奥要从A+B处背着公主以最短路程到达1处，其中1-A是村庄，剩下的是城堡

 //        有可使用K次可飞过L长的靴子（每次都以结点开始或结束），求最短路长

 //首先需要得到任意两点之间的最短路-Floyd较为简便(10^5次操作也能接受)

 //其次需要利用BFS从A+B处开始遍历并进行状态转移-BFS+DP

 //构造状态：DP[i][k]:从i到A+B经过k次瞬移得到的最短路

 //状态转移方程：

 //能够从x瞬移到y：dp[x][k] = min(dp[x][k], dp[y][k - 1], dp[y][k] + d[x][y])

 //不能从x瞬移到y：dp[x][k] = min(dp[x][k], dp[y][k] + d[x][y])

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<queue>

 #include<vector>

 using namespace std;

 #define INF 0x3f3f3f3f

 #define MAX 105

 vector<int> e[MAX];    //邻接表

 int A, B, M, L, K;

 int d[MAX][MAX];    //distance

 bool fly[MAX][MAX];    //能否瞬移

 int vis[MAX];

 int dp[MAX][];    //dp[i][k]:从i到A+B经过k次瞬移得到的最短路

 void floyd(int N)

 {

     for (int i = ; i <= N; i++)

         d[i][i] = ;

     for (int k = ; k <= N; k++)

         for (int i = ; i <= N; i++)

             for (int j = ; j <= N; j++)

                 if (d[i][j] > d[i][k] + d[k][j])

                 {

                     d[i][j] = d[i][k] + d[k][j];

                     if (k <= A && d[i][j] <= L)

                     {

                         fly[i][j] = true;

                         e[i].push_back(j);

                     }

                 }

 }

 int main()

 {

     //freopen("in.txt", "r", stdin);

     //freopen("out-2.txt", "w", stdout);

     int T;

     scanf("%d", &T);

     while (T--) {

         memset(d, INF, sizeof(d));

         memset(fly, false, sizeof(fly));

         memset(e, , sizeof(e));

         scanf("%d%d%d%d%d", &A, &B, &M, &L, &K);

         while (M--) {

             int u, v, w;

             scanf("%d%d%d", &u, &v, &w);

             d[v][u] = d[u][v] = w;

             e[v].push_back(u);

             e[u].push_back(v);

             if (w <= L)    fly[u][v] = fly[v][u] = true;

         }

         floyd(A + B);

         //类似SPFA的过程(BFS)

         memset(dp, INF, sizeof(dp));

         for (int i = ; i <= K; i++)

             dp[A + B][i] = ;

         for (int i = ; i <= A + B; i++)

             dp[i][] = d[i][A + B];

         for (int k = ; k <= K; k++)

         {

             memset(vis, false, sizeof(vis));

             queue<int> q;

             q.push(A + B);    //从A+B开始遍历

             vis[A + B] = true;

             while (!q.empty()) {

                 int cur = q.front();

                 q.pop();

                 for (int i = ; i < e[cur].size(); i++)

                 {

                     int u = e[cur][i];

                     int tmp = dp[u][k];

                     //状态转移

                     if (fly[u][cur])    //可瞬移

                         dp[u][k] = min(dp[u][k], dp[cur][k - ]);

                     dp[u][k] = min(dp[u][k], dp[cur][k] + d[cur][u]);

                     //需要转移状态的条件 - 没有访问过 or 最短路长变更

                     if (!vis[u] || tmp != dp[u][k])

                         q.push(u);

                     vis[u] = true;

                 }

             }

         }

         printf("%d\n", dp[][K]);

     }

     return ;

 }