UVA 12047

#define ll long long
#include <bits/stdc++.h>
using namespace std;

const int OO = 1e9;
const double EPS = 1e-9;
ll mem[2][10000];

class edge {
    public:
    int from;
    int to;
    ll w;

    edge(int f, int t, ll wt) {
        from = f;
        to = t;
        w = wt;
    }

    bool operator < (const edge &e) const {
        return w > e.w;
    }
};

vector<vector<edge>> graph1;
vector<vector<edge>> graph2;
ll n,m,s,d,p;



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while(t--) {
        cin >> n >> m >> s >> d >> p;
        s--;
        d--;
        graph1.clear();
        graph1.resize(n);
        graph2.clear();
        graph2.resize(n);
        memset(mem,-1,sizeof(mem));
        priority_queue<edge> all;
        for(int i = 0; i < m; i++) {
            ll u,v,c;
            cin >> u >> v >> c;
            u--,v--;
            graph1[u].push_back(edge(u,v,c));
            graph2[v].push_back(edge(v,u,c));
            all.push(edge(u,v,c));
        }
        priority_queue<edge> pq;
        pq.push(edge(s,s,0));
        while(!pq.empty()) {
            edge curr = pq.top();
            pq.pop();
            if(mem[0][curr.to] == -1) {
                mem[0][curr.to] = curr.w;
                for(edge &e : graph1[curr.to]) {
                    pq.push(edge(curr.to,e.to,curr.w + e.w));
                }
            }
        }
        pq.push(edge(d,d,0));
        while(!pq.empty()) {
            edge curr = pq.top();
            pq.pop();
            if(mem[1][curr.to] == -1) {
                mem[1][curr.to] = curr.w;
                for(edge &e : graph2[curr.to]) {
                    pq.push(edge(curr.to,e.to,curr.w + e.w));
                }
            }
        }
        ll ans = -1;
        while(!all.empty()) {
            edge curr = all.top();
            all.pop();
            if(mem[0][curr.from] != -1 && mem[1][curr.to] != -1
               && mem[0][curr.from] + mem[1][curr.to] + curr.w <= p)
                ans = curr.w;
        }
        cout << ans << "\n";
    }
    return 0;
}