Super Mario

#include <bits/stdc++.h>

#define INF 2139062143
#define MAX 100
#define debug(x) cout << #x << " = " << x << endl
#define fori(i, ini, lim) for(int i= int(ini); i<(int)lim; ++i)
#define ford(i, ini, lim) for(int i= int(ini); i>=(int)lim; --i)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, pair<int, ii> > pii;
int a, b, K, m, l;

int dist[MAX+5][15][505];
vector<ii> adj[MAX+5];

void dij(int s){
    priority_queue<pii, vector<pii>, greater<pii> > pq;
    dist[s][0][0] = 0; // vertex, k, quilometros left
    pq.push(pii(0,make_pair(s, ii(0,0)))); // weight, vertex, k = how many times the boots were used, quilometros left
    while(!pq.empty()){
        pii cur = pq.top(); pq.pop();
        int u = cur.second.first;
        int w = cur.first;
        int k = cur.second.second.first;
        int isk = cur.second.second.second;

        if(w > dist[u][k][isk]) continue;
        fori(i,0,adj[u].size()){
            ii cadj = adj[u][i];
            int v = cadj.first;
            int nw = cadj.second;
            // do not use the magic boots
            if(dist[u][k][isk] + nw < dist[v][k][isk]){
                dist[v][k][isk] = dist[u][k][isk] + nw;
                pq.push(pii(dist[v][k][isk],make_pair(v, ii(k,0))));
            }
            // is in the middle of the run, so keep runing
            if(isk >= nw && u <= a){
                if(dist[u][k][isk] < dist[v][k][isk-nw]){
                    dist[v][k][isk-nw] = dist[u][k][isk];
                    pq.push(pii(dist[v][k][isk-nw],make_pair(v, ii(k,isk-nw))));
                }
            }
            // start a new run with the magic boots
            if(k < K && l >= nw){
                if(dist[u][k][0] < dist[v][k+1][l-nw]){
                    dist[v][k+1][l-nw] = dist[u][k][0];
                    pq.push(pii(dist[v][k+1][l-nw],make_pair(v, ii(k+1,l-nw))));
                }
            }
cout << "u: " << u << " v: " << v << " nw: " << nw << " dist[u]: " << dist[u][k][isk] << " dist[v]: " << dist[v][k][isk] << " k: " << k << " isk: " << isk << endl;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);

    int t; cin >> t;
    while(t--){
        cin >> a >> b >> m >> l >> K;
        fori(i,0,a+b+1){
            adj[i].clear();
        }
        fori(i,0,m){
            int x, y, w; cin >> x >> y >> w;
            adj[x].emplace_back(y,w);
            adj[y].emplace_back(x,w);
        }
        memset(dist, 0x7F, sizeof(dist));
        dij(a+b);
        int ans = INF;
        fori(j, 0, l){
            fori(i, 0, K+1){
                ans = min(ans, dist[1][i][j]);
            }
        }
        cout << ans << endl;
    }

    return 0;
}