#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <array>
using namespace std;

struct node
{
    int idx;
    int time;
    int cost;

    node(){}
    node(int _idx, int _time, int _cost)
    {
        idx=_idx;
        time=_time;
        cost=_cost;
    }
    bool operator<(const node &tmp) const
    {
        return time>tmp.time;
    }
};
int d[3005][2005];

int main()
{
//    ifstream cin("in.txt");
    int s,a,n;
    cin>>s>>a>>n;
    int x,y,t,m;
    vector<array<int,3>>par[a+5];
    for(int i=0;i<n;i++)
    {
        cin>>x>>y>>t>>m;
        par[x].push_back({y,t,m});
        par[y].push_back({x,t,m});
    }
    priority_queue<node>Q;
    Q.push(node(1,0,0));
    for(int i=0;i<=a;i++)
    {
        for(int j=0;j<=s;j++)
        {
            d[i][j]=2e9;
        }
    }
    d[1][0] = 0;
    while(!Q.empty())
    {
        node teme=Q.top();
        Q.pop();
        for(int i=0;i<par[teme.idx].size();i++)
        {
            int sosed=par[teme.idx][i][0];
            int pat=par[teme.idx][i][1];
            int cena=par[teme.idx][i][2];
            if(cena + teme.cost <= s and pat + teme.time < d[sosed][cena + teme.cost])
            {
                d[sosed][cena + teme.cost]=pat+teme.time;
                Q.push(node(sosed,pat + teme.time , cena + teme.cost));
            }
        }
    }
    int najmal=2e9;
    for(int i=0;i<=s;i++)
    {
        najmal = min(najmal, d[a][i]);
    }
    if(najmal == 2e9) {
        najmal = -1;
    }
    cout << najmal << endl;
    return 0;
}