#include<bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

struct Edge { int v, c, d; };

int N, C, M;
int D[50][301];
vector<Edge> E[50];
const int INF = 1000000000;

int main() {
    cin >> N >> C >> M;
    {
        int Ebuf[1500][4]; rep(j, 4) rep(i, M) cin >> Ebuf[i][j];
        rep(i, M) E[Ebuf[i][0] - 1].push_back({ Ebuf[i][1] - 1,Ebuf[i][2],Ebuf[i][3] });
    }

    rep(i, N) rep(j, C + 1) D[i][j] = INF;
    priority_queue<pair<int, pair<int, int>>> Q; Q.push({ 0,{0,C} });
    while (Q.size()) {
        int d = Q.top().first;
        int p = Q.top().second.first;
        int c = Q.top().second.second; Q.pop();
        if (D[p][c] != INF) continue;
        D[p][c] = -d;
        for (Edge& e : E[p]) {
            if (c < e.c) continue;
            Q.push({ d - e.d, {e.v, c - e.c} });
        }
    }

    int ans = INF;
    rep(i, C + 1) ans = min(ans, D[N - 1][i]);
    if (ans == INF) cout << -1 << endl;
    else cout << ans << endl;

    return 0;
}