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

#define pii pair<int, int>
#define pipii pair<int, pii >
#define pqpipii priority_queue<pipii, vector<pipii >, greater<pipii > >

vector<vector<int> > path;
vector<vector<int> > tx;
vector<vector<int> > hx;

int hull[2048];

int solve(int from, int to, int n, int k) {

    pqpipii pq;
    pq.push(make_pair(0, make_pair(0, from)));

    while (!pq.empty()) {
        pipii curr = pq.top();
        pq.pop();

        int dist = curr.first;
        int wear = curr.second.first;
        int loc = curr.second.second;

        if (wear >= k) continue;
        if (hull[loc] >= (k - wear)) continue;

        if (loc == to) return dist;

        hull[loc] = k - wear;

        for (int i = 0; i < path[loc].size(); ++i) {
            pq.push(make_pair(dist + tx[loc][i], make_pair(wear + hx[loc][i], path[loc][i])));
        }
    }

    return -1;
}

int main() {
    int k, n, m;
    cin >> k >> n >> m;

    memset(hull, 0, sizeof(hull));

    for (int i = 0; i <= n; ++i) {
        path.push_back(vector<int>());
        tx.push_back(vector<int>());
        hx.push_back(vector<int>());
    }

    for (int i = 0; i < m; ++i) {
        int a, b, t, h;
        cin >> a >> b >> t >> h;

        path[a].push_back(b);
        tx[a].push_back(t);
        hx[a].push_back(h);

        path[b].push_back(a);
        tx[b].push_back(t);
        hx[b].push_back(h);
    }

    int a, b;
    cin >> a >> b;

    cout << solve(a, b, n, k) << endl;
}