#include 
 
using namespace std;
const int maxn = 1e5 + 10;
const int INF = (1 << 30);
typedef long long ll;
const ll inf = (1LL << 59LL);
struct node{
    int till, euro, time;
    node (){}
    node(int _t, int _timee, int _e){
        till = _t;
        time = _timee;
        euro = _e;
    }
};
vector graph[5005];
int n, m, S;
bool visited[3005][6005];
int idx[3005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> S >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a--; b--;
        graph[a].push_back(node(b, c, d));
        graph[b].push_back(node(a, c, d));
    }
    memset(visited, false, sizeof visited);
   int  min_vreme = INF;
    queue q;
    q.push(0);
    q.push(0);
    q.push(0);
    int sosed;
    int weight, money;
    int eee;
    while(!q.empty()){
        int teme = q.front();
        q.pop();
        int pari = q.front();
        q.pop();
        int pat = q.front();
        q.pop();
        if(teme == n - 1){
            if(pat <= S){
                min_vreme = min(min_vreme, pari);
            }
            continue;
        }
        for(int i = 0; i < (int)graph[teme].size(); i++){
            sosed = graph[teme][i].till;
            money = graph[teme][i].time;
            weight = graph[teme][i].euro;
            if(weight + pat <= S){
                    eee = money + pari;
            if(eee >= 6000) eee -= 6000;
                if(!visited[sosed][eee]){
                    visited[sosed][eee] = true;
                    q.push(sosed);
                    q.push(pari + money);
                    q.push(pat + weight);
                }
            }
        }
 
    }
 
    q.push(0);
    q.push(0);
    q.push(0);
    memset(visited, false, sizeof visited);
    while(!q.empty()){
        int teme = q.front();
        q.pop();
        int pari = q.front();
        q.pop();
        int pat = q.front();
        q.pop();
        if(teme == n - 1){
            if(pat <= S){
                min_vreme = min(min_vreme, pari);
            }
            continue;
        }
        for(int i = 0; i < (int)graph[teme].size(); i++){
            sosed = graph[teme][i].till;
            money = graph[teme][i].time;
            weight = graph[teme][i].euro;
            if(weight + pat <= S){
                    eee = pat + weight;
                if(eee >= 6000){
                    eee -= 6000;
                }
                if(!visited[sosed][pat + weight]){
                    visited[sosed][pat + weight] = true;
                    q.push(sosed);
                    q.push(pari + money);
                    q.push(pat + weight);
                }
            }
        }
 
    }
        q.push(0);
    q.push(0);
    q.push(0);
    memset(idx, 0, sizeof idx);
    memset(visited, false, sizeof visited);
    while(!q.empty()){
        int teme = q.front();
        q.pop();
        int pari = q.front();
        q.pop();
        int pat = q.front();
        q.pop();
        if(teme == n - 1){
            if(pat <= S){
                min_vreme = min(min_vreme, pari);
            }
            continue;
        }
        for(int i = 0; i < (int)graph[teme].size(); i++){
            sosed = graph[teme][i].till;
            money = graph[teme][i].time;
            weight = graph[teme][i].euro;
            if(weight + pat <= S){
                    eee = idx[sosed] + 1;
                    if(eee >= 6000){
                        eee -= 6000;
                    }
                    idx[sosed]++;
                if(!visited[sosed][pat + weight]){
                    visited[sosed][pat + weight] = true;
                    q.push(sosed);
                    q.push(pari + money);
                    q.push(pat + weight);
                }
            }
        }
 
    }
 
 
 
    if(min_vreme == INF){
        cout << -1 << endl;
        return 0;
    }
    cout << min_vreme << endl;
    return 0;
}