#include <vector>
#include <queue>
#include <deque>
#include <stdio.h>
#include <unordered_set>
#include <utility>
#include <string.h>
#include <limits>
using namespace std;

#define MAXN 1010
#define MAXK 80
#define MAXV 1000000

struct arco_t {
    int u, v;
    int t_piedi;
    int t_bus;
    int n_volontarie;
};
struct info_t {
    int n, t, k;
    bool operator< (const info_t& r) const {
        return t > r.t;
    }
};

const int INF = numeric_limits<int>::max();

int N, T, S, E, K;

vector<vector<arco_t>> G;

int dist[MAXN][MAXK];
bool solved[MAXN][MAXK];
bool dijkstra(int v_max) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= K; j++) {
            dist[i][j] = INF;
            solved[i][j] = false;
        }
    }
    priority_queue<info_t> Q;
    Q.push({S, 0, K});
    dist[S][K] = 0;
    while (!Q.empty()) {
        info_t c = Q.top();
        Q.pop();

        //printf("Nodo %d @ t: %d, k:%d\n", c.n, c.t, c.k);
        if (c.n == E) return true;

        solved[c.n][c.k] = true;

        // Se sto visitando questo nodo con un tempo minore dell'ultima volta
        for (const arco_t& x : G[c.n]) {

            //printf("\tArco %d (t: %d, b: %d, v: %d)\n", x.v, x.t_piedi, x.t_bus, x.n_volontarie);
            if (c.k > 0 && dist[x.v][c.k-1] > c.t + x.t_bus) {

                // Se con l'autobus faccio in tempo ed ho almeno 1 biglietto
                if (c.t + x.t_bus < T && c.k > 0 && !solved[x.v][c.k-1]) {
                    // Aggiungo alla lista
                    Q.push({x.v, c.t+x.t_bus, c.k-1});
                }

            }
            if (dist[x.v][c.k] > c.t + x.t_piedi) {

                // Se a piedi faccio in tempo e ci sono al massimo v_max volontarie
                if (c.t + x.t_piedi < T && x.n_volontarie <= v_max && !solved[x.v][c.k]) {
                    // Aggiungo alla lista
                    Q.push({x.v, c.t+x.t_piedi, c.k});
                }
            }
        }

    }
    return false;
}

int avoid_volunteers(int subtask, int N, int M, int K, int S, int E, int T, int A[], int B[], int W[], int P[], int V[]) {
    ::N = N;
    ::T = T;
    ::E = E;
    ::K = K;
    ::S = S;
    G.resize(N);
    int v_max = 0;
    for (int i = 0; i < M; i++) {
        v_max = max(v_max, V[i]);
        G[A[i]].push_back({A[i], B[i], W[i], P[i], V[i]});
        G[B[i]].push_back({B[i], A[i], W[i], P[i], V[i]});
    }

    int start = 0;
    int end = MAXV;


    int last = INF;
    while (start <= end) {
        int mid = (start+end) / 2;
        bool r = dijkstra(mid);
        //printf("mid(%d) = %d\n", mid, r);
        if (r == 1) {
            last = min(mid, last);
            end = mid-1;
        }
        else {
            start = mid+1;
        }
    }
    return (last == INF ? -1 : last);
}