#include<stdio.h>const int maxn = 150;const int INF = 1000000000;int mat[maxn][maxn],tmp[maxn][maxn],Dist[maxn];int DP[maxn][20],newmat[maxn][maxn];bool visited[maxn];int n,A,B,L;void Dijstra(int s){int i,j,k,min;for(i=1;i<=n;i++){Dist[i] = mat[s][i];visited[i] = false;}Dist[s] = 0;visited[s] = true;for(i=1;i<=n;i++){k = -1;min = INF;for(j=1;j<=n;j++)if(visited[j]==false&&min>Dist[j]){k = j;min = Dist[j];}if(k!=-1){visited[k] = true;for(j=1;j<=n;j++){if(Dist[k]+mat[k][j]<Dist[j]){Dist[j] = Dist[k] + mat[k][j];}}}}}void Dijstra1(int s)//为了求tmp[][],tmp[][]保存的是任意两点是否能穿鞋子通过。{int i,j,k,min;for(i=1;i<=n;i++){Dist[i] = mat[s][i];visited[i] = false;}Dist[s] = 0;visited[s] = true;for(i=1;i<=n;i++){k = -1;min = INF;for(j=1;j<=n;j++)if(visited[j]==false&&min>Dist[j]){k = j;min = Dist[j];}if(k!=-1){visited[k] = true;for(j=1;j<=n;j++){if(Dist[k]+mat[k][j]<Dist[j]&&k<=A){Dist[j] = Dist[k]+mat[k][j];if(Dist[j]<=L)tmp[s][j] = 0;}}}}}int main(){int i,j,t,m,K;scanf("%d",&t);while(t--){scanf("%d%d%d%d%d",&A,&B,&m,&L,&K);n = A+B;for(i=1;i<=n;i++)for(j=1;j<=n;j++)mat[i][j] = newmat[i][j] = tmp[j][i] = INF;//初始化int a,b,c;for(i=0;i<m;i++){scanf("%d%d%d",&a,&b,&c);mat[a][b] = mat[b][a] = c;if(c<=L)tmp[a][b] = tmp[b][a] = 0;newmat[a][b] = newmat[b][a] = c;}//构图for(i=1;i<=n;i++){Dijstra1(i);Dijstra(i);for(j=1;j<=n;j++)newmat[i][j] = Dist[j];}for(i=1;i<=n;i++)DP[i][0] = newmat[1][i];//未使用加速靴时的时间for(j=1;j<=K;j++)DP[1][j] = 0; for(i=2;i<=n;i++){for(j=1;j<=K;j++){int min = INF,tt;for(int l = 1;l<i;l++){if(!tmp[l][i])tt = DP[l][j-1]>DP[l][j]+newmat[l][i]?DP[l][j]+newmat[l][i]:DP[l][j-1];else tt = newmat[l][i]+DP[l][j];if(tt<min)min = tt;}DP[i][j] = min;}}printf("%dn",DP[n][K]);}return 0;}
