#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std ;
struct  node{
    int index,najmal_pat,money;

    node(int i,int p,int m){
        index = i;
        najmal_pat = p;
            money = m;
    }
    bool  operator < (const node &tmp)const {
        return najmal_pat > tmp.najmal_pat;
    }
};
int dist[3005][2005];
int main() {
int S, N , M;
cin >> S >> N >> M;
vector<node> graph[N+5];
    for (int i = 0; i < M; i++) {
        int v,w,t,e;
        cin >> v >> w >> t >> e;
        graph[v].push_back(node(w,t,e));
        graph[w].push_back(node(v,t,e));
    }
    priority_queue<node> pq;
    pq.push(node(1,0,0));
    for (int i = 0; i < 3005; i++) {
        for (int j = 0; j < 2005; j++) {
            dist[i][j] = 2e9;
        }
    }
    dist[1][0] = 0;
    while(!pq.empty()){
        node current = pq.top();
        pq.pop();

        for (int i = 0; i < graph[current.index].size(); i++) {
            int sosed = graph[current.index][i].index;
            int pat = graph[current.index][i].najmal_pat;
            int pari = graph[current.index][i].money;

            if(pari+current.money <= S && current.najmal_pat + pat < dist[sosed][pari+current.money]){
                dist[sosed][pari + current.money] = current.najmal_pat + pat;
                pq.push(node(sosed,current.najmal_pat +pat,current.money + pari));
            }
        }
    }
    int rezultat= 2e9;
    for (int i = 0; i <= S; i++) {
        rezultat = min(dist[N][i], rezultat);
    }
    if (rezultat == 2e9){
        cout << "-1";
    }
    else
        cout << rezultat << endl;
}