#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}#define MAXN 110const int INF = 0x3f3f3f3f ;int dis[MAXN][MAXN];int A,B,M,L,K;int dp[MAXN][MAXN];bool inq[MAXN][MAXN];struct node{    int idx;    int cnt;};void read(){    scanf("%d%d%d%d%d",&A,&B,&M,&L,&K);    memset(dis,0x3f,sizeof(dp));    for (int i = 0; i <= A + B; i++) dis[i][i] = 0;    while (M--)    {        int u,v,w;        scanf("%d%d%d",&u,&v,&w);        dis[u][v] = dis[v][u] = w;    }    for (int k = 1; k <= A; k++)        for (int i = 1; i <= A + B; i++)          for (int j = 1; j <= A + B; j++)          dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);}void SPFA(){    memset(inq,false,sizeof(inq));    memset(dp,0x3f,sizeof(dp));    queue<node>q; while (!q.empty()) q.pop();    node tmp;    tmp.cnt = K; tmp.idx = A + B;    inq[A + B][K] = true;    dp[A + B][K] = 0;    q.push(tmp);    while (!q.empty())    {        node tmp = q.front(); q.pop();        int u = tmp.idx , num = tmp.cnt;        inq[u][num] = false;        //printf("%d %d \n",u,num);        for (int i = 1; i <= A + B; i++)        {            if (i == u) continue;            if (dis[u][i] != INF)            {          //      printf("dis[%d][%d] = %d\n",u,i,dis[u][i]);          //      printf("%d\n",dp[i][num - 1]);                if (num > 0 && dis[u][i] <= L && dp[i][num - 1] > dp[u][num])                {                    dp[i][num - 1] = dp[u][num];                    if (!inq[i][num - 1])                    {                        inq[i][num - 1] = true;                        node temp;                        temp.idx = i;                        temp.cnt = num - 1;                        q.push(temp);                    }                }                if (dp[i][num] > dp[u][num] + dis[u][i])                {                    dp[i][num] = dp[u][num] + dis[u][i];                    if (!inq[i][num])                    {                        inq[i][num] = true;                        node temp;                        temp.idx = i;                        temp.cnt = num;                        q.push(temp);                    }                }            }        }    }    int ans = INT_MAX;    for (int i = 0; i <= K; i++)        ans = min(ans,dp[1][i]);    printf("%d\n",ans);}int main(){   // freopen("sample.txt","r",stdin);    int T;    scanf("%d",&T);    while (T--)    {        read();        SPFA();    }    return 0;}