import java.util.*;
import java.io.*;

public class HH {
    FastScanner in;
    PrintWriter out;

    ArrayList<Integer> lens;

    int[][] flow, cap;

    void findMinCostPaths() {
        int n = flow.length;
        int[] h = new int[n];
        Arrays.fill(h, 0);
        final int[] d = new int[n];
        int[] last = new int[n];
        int st = 0, en = n - 1;
        boolean[] was = new boolean[n];
        while (true) {
            Arrays.fill(d, Integer.MAX_VALUE);
            Arrays.fill(last, -1);
            Arrays.fill(was, false);
            d[st] = 0;
            while (true) {
                int v = -1;
                for (int i = 0; i < n; i++) {
                    if (!was[i]) {
                        if (d[i] != Integer.MAX_VALUE
                                && (v == -1 || d[v] > d[i])) {
                            v = i;
                        }
                    }
                }
                if (v == -1) {
                    break;
                }
                was[v] = true;
                for (int to = 0; to < n; to++) {
                    if (was[to] || flow[v][to] == cap[v][to]) {
                        continue;
                    }
                    int newCost = flow[v][to] < 0 ? -1 : 1;
                    newCost += d[v] + h[v] - h[to];
                    if (d[to] > newCost) {
                        d[to] = newCost;
                        last[to] = v;
                    }
                }
            }
            if (d[en] == Integer.MAX_VALUE)
                break;
            for (int i = 0; i < n; i++) {
                if (d[i] != Integer.MAX_VALUE)
                    h[i] += d[i];
            }
            int v = en;
            int len = 0;
            int max = Integer.MAX_VALUE;
            while (v != st) {
                int prev = last[v];
                max = Math.min(max, flow[prev][v] < 0 ? -flow[prev][v]
                        : cap[prev][v] - flow[prev][v]);
                v = prev;
            }
            v = en;
            while (v != st) {
                int prev = last[v];
                len += flow[prev][v] < 0 ? -1 : 1;
                flow[prev][v] += max;
                flow[v][prev] -= max;
                v = prev;
            }
            for (int i = 0; i < max; i++) {
                lens.add(len);
            }
        }
    }

    public void solve() throws IOException {
        int n = in.nextInt();
        int k = in.nextInt();
        lens = new ArrayList<Integer>();
        flow = new int[n][n];
        cap = new int[n][n];
        for (int i = 0; i < k; i++) {
            int a = in.nextInt() - 1, b = in.nextInt() - 1, c = in.nextInt();
            cap[a][b] = cap[b][a] = c;
        }
        int t = in.nextInt();
        long f = in.nextInt();
        if (n == 1) {
            out.println(0);
            return;
        }
        findMinCostPaths();
        // Collections.sort(lens);
        int daysL = 0, daysR = t + n;
        while (daysR - daysL > 1) {
            int days = (daysL + daysR) / 2;
            int dudes = t;
            long money = 0;
            for (int len : lens) {
                long toGo = Math.min(dudes, days - len + 1);
                if (toGo < 0)
                    continue;
                money += toGo * len;
                dudes -= toGo;
            }
            if (money <= f && dudes == 0)
                daysR = days;
            else
                daysL = days;
        }
        if (daysR == t + n)
            daysR = -1;
        out.println(daysR);
    }

    public void run() {
        try {
            in = new FastScanner();
            out = new PrintWriter(System.out);

            int tests = in.nextInt();
            for (int i = 0; i < tests; i++)
                solve();

            out.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    public static void main(String[] arg) {
        new HH().run();
    }
}