#include <cstring>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

typedef long long i64;

struct trio
{
    int to, cap, cost;

    trio();
    trio(int _to, int _cap, int _cost)
    {
        to = _to;
        cap = _cap;
        cost = _cost;
    }
};

typedef vector<trio> VT;
#define push_trio(def1, def2, def3) push_back(trio(def1, def2, def3))

const i64 INF = 1LL << 32;

int X, N, M, T;
i64 Dist[10002];
VT V[10002];
queue<int> Q;
bool inQ[10002];

bool Test(i64 mincap)
{
    for (int i = 2; i <= N; ++i)
        Dist[i] = INF;
    Dist[1] = 0;

    Q.push(1);
    inQ[1] = true;

    while (!Q.empty())
    {
        int now = Q.front(); Q.pop();
        inQ[now] = false;

        for (VT::iterator it = V[now].begin(); it != V[now].end(); ++it)
            if (it->cap >= mincap && Dist[now] + (i64) it->cost < Dist[it->to])
            {
                Dist[it->to] = Dist[now] + it->cost;
                if (!inQ[it->to])
                {
                    inQ[it->to] = true;
                    Q.push(it->to);
                }
            }
    }

    return Dist[N] <= T;
}

int main()
{
    ifstream fin("dcmcp.in");
    ofstream fout("dcmcp.out");

    fin >> X;
    while (X--)
    {
        fin >> N >> M >> T;
        for (int i = 1, A, B, C, D; i <= M; ++i)
        {
            fin >> A >> B >> C >> D;
            V[A].push_trio(B, C, D);
            V[B].push_trio(A, C, D);
        }

        i64 step = 1LL << 32, maxcap;
        for (maxcap = 0; step; step >>= 1)
            if (maxcap + step <= (1LL << 32) && Test(maxcap + step))
                maxcap += step;

        fout << maxcap << '\n';

        for (int i = 1; i <= N; ++i)
            V[i].clear();
    }

    fin.close();
    fout.close();
}