#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct node{
int distance;
int cena;
int index;

node(){


}

node(int _index, int _distance, int _cena){
index=_index;
distance=_distance;
cena=_cena;
}

bool operator <(const node&tmp)const{
return distance > tmp.distance;
}





};
int main()
{
    int n;
    int m;
    int S;
    int S1=200000000;


    cin>>S;
    cin>>n>>m;
    int matrica[n+1][S + 1];
    vector<node>v[n+1];

    for(int x1=0; x1<n+1; x1++){
        for(int s1=0; s1<= S; s1++){
            matrica[x1][s1]=2000000000;
        }

    }
    for(int x=0; x<m; x++){
    int indexa;
    int indexb;
    int distance;
    int cost;
    cin>>indexa>>indexb>>distance>>cost;
    v[indexa].push_back(node(indexb, distance, cost));
    v[indexb].push_back(node(indexa, distance, cost));
    }
    priority_queue<node>pq;
    pq.push(node(1, 0, 0));

    matrica[1][0]=0;

    while(!pq.empty()){
    node cnode=pq.top();
    pq.pop();
    for(int h=0; h<v[cnode.index].size(); h++){
    int  sosed=v[cnode.index][h].index;
    int distance=v[cnode.index][h].distance;
    int cena=v[cnode.index][h].cena;
    if((cena+cnode.cena<=S)and(matrica[sosed][cena+cnode.cena]>distance+cnode.distance)){
    matrica[sosed][cena+cnode.cena]=distance+cnode.distance;
    pq.push(node(sosed, distance+cnode.distance, cena+cnode.cena));
    }
    }


    }
     for(int y=0; y<=S; y++){
     if(matrica[n][y]<S1){
     S1=matrica[n][y];
     }
     }
    if(S1 == 200000000) {
        S1 = -1;
    }
    cout<<S1;
    return 0;
}