#include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 #include <stdlib.h>

 #include <vector>

 #include <queue>

 #include <stack>

 #define loop(s,i,n) for(i = s;i < n;i++)

 #define cl(a,b) memset(a,b,sizeof(a))

 const int maxn = ;

 const int inf = ;

 using namespace std;

 struct node

 {

     int u,v,len,cost;

     int next;

 }edges[];

 int g[];

 int vis[];

 int ans;

 int n,m;

 void dfs(int u,int val,int dis)

 {

     vis[u] = ;

     if(val < )

     return;

     if(u == n)

     {

         if(ans > dis)

         ans = dis;

         return ;

     }

     if(ans < dis)

     return;

     int i;

     for(i = g[u];i != -;i = edges[i].next)

     {

         int v;

         v = edges[i].v;

         int len,cost;

         len = edges[i].len;

         cost = edges[i].cost;

         if(!vis[v])

         {

             dfs(v,val-cost,dis+len);

             vis[v]--;

         }

     }

 }

 int main()

 {

     int u,v,l,t;

     int k;

     while(~scanf("%d %d %d",&k,&n,&m))

     {

         int i;

         memset(vis,,sizeof(vis));

         cl(g,-);

         int cnt = ;

         while(m--)

         {

             scanf("%d%d%d%d",&u,&v,&l,&t);

             edges[cnt].u = u;

             edges[cnt].v = v;

             edges[cnt].len = l;

             edges[cnt].cost = t;

             edges[cnt].next = g[u];

             g[u] = cnt;

             cnt++;

         }

         ans = inf;

         dfs(,k,);

         if(ans != inf)

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

         else

         puts("-1");

     }

     return ;

 }