ROADS

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

const int N = 105;
const int oo = 1e9 + 7;

struct node {
    int root, dist, cost;
};

bool operator > (node a, node b) {
    return a.cost > b.cost;
}

int k, n, m;
vector<node> a[N];

int d[N];

void dijkstra() {
    priority_queue<node, vector<node>, greater<node>> pq;
    fill(d + 1, d + n + 1, oo);
    pq.push({1, 0, 0});

    while(!pq.empty()) {
        int u = pq.top().root;
        int du = pq.top().dist;
        int costu = pq.top().cost;
        pq.pop();

        if(du >= d[u]) continue;

        d[u] = du;
        for(int i = 0; i < a[u].size(); i++) {
            int v = a[u][i].root;
            int w = a[u][i].dist;
            int c = a[u][i].cost;

            if(costu + c > k) continue;
            pq.push({v, du + w, costu + c});
        }
    }
}

int main() {
    //freopen("in.txt", "r", stdin);
    //freopen("ROADS.inp", "r", stdin);
    //freopen("ROADS.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int t; cin >> t;
    while(t--) {
        cin >> k >> n >> m;
        for (int i = 1; i <= n; i++)
            a[i].clear();

        for(int i = 1; i <= m; i++) {
            int u, v, w, c;
            cin >> u >> v >> w >> c;
            a[u].push_back({v, w, c});
        }

        dijkstra();

        if(d[n] == oo) d[n] = -1;
        cout << d[n] << '\n';
    }

    return 0;
}