#include <iostream>

 #include <vector>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #include <map>

 #include <set>

 #include <string>

 #include <queue>

 using namespace std;

 #define pb(x) push_back(x)

 #define ll long long

 #define mk(x, y) make_pair(x, y)

 #define lson l, m, rt<<1

 #define mem(a) memset(a, 0, sizeof(a))

 #define rson m+1, r, rt<<1|1

 #define mem1(a) memset(a, -1, sizeof(a))

 #define mem2(a) memset(a, 0x3f, sizeof(a))

 #define rep(i, a, n) for(int i = a; i<n; i++)

 #define ull unsigned long long

 typedef pair<int, int> pll;

 const double PI = acos(-1.0);

 const double eps = 1e-;

 const int mod = 1e9+;

 const int inf = ;

 const int dir[][] = { {-, }, {, }, {, -}, {, } };

 const int maxn = 1e5+;

 int head[maxn], k, n, num, dis[][];

 struct node

 {

     int to, nextt, cost, d;

 }e[maxn*];

 void init() {

     num = ;

     mem1(head);

 }

 void add(int u, int v, int cost, int d) {

     e[num].to = v;

     e[num].nextt = head[u];

     e[num].cost = cost;

     e[num].d = d;

     head[u] = num++;

 }

 struct ee

 {

     int u, d, cost;

     bool operator < (ee a)const

     {

         if(d == a.d)

             return cost>a.cost;

         return d>a.d;

     }

     ee(){}

     ee(int u, int d, int cost):u(u), d(d), cost(cost){}

 };

 int dij() {

     priority_queue <ee> q;

     mem2(dis);

     dis[][] = ;

     q.push(ee(, , ));

     while(!q.empty()) {

         ee tmp = q.top(); q.pop();

         if(tmp.u == n)

             return tmp.d;

         for(int i = head[tmp.u]; ~i; i = e[i].nextt) {

             int v = e[i].to;

             if(dis[v][tmp.cost+e[i].cost]>tmp.d+e[i].d) {

                 if(tmp.cost+e[i].cost<=k) {

                     q.push(ee(v, tmp.d+e[i].d, tmp.cost+e[i].cost));

                     dis[v][tmp.cost+e[i].cost] = tmp.d+e[i].d;

                 }

             }

         }

     }

     return -;

 }

 int main()

 {

     int m, u, v, w, c;

     while(cin>>k) {

         cin>>n>>m;

         init();

         while(m--) {

             scanf("%d%d%d%d", &u, &v, &w, &c);

             add(u, v, c, w);

         }

         int ans = dij();

         printf("%d\n", ans);

     }

     return ;

 }