#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 105;
const int M = 101;
const int MAX = 1000000000;
struct edge
{
   int u,v,l,w,next;
}e[N*N];
int first[N],t=-1;
void add(int u, int v, int l, int w)
{
   t++;
   e[t].u = u;
   e[t].v = v;
   e[t].l = l;
   e[t].w = w;
   e[t].next = first[u];
   first[u] = t;
}
int n,k,r;
int min_cost[N][N];//the minist cost from every node to the destination
int min_road[N][N];//the minist path from every node to the destination
int best = MAX; //the shortest from the source to the destination
bool visit[N];
bool flag;
void floyd()
{
   for(int i = 1; i <= n; i++)
   {
      for(int j = 1; j <= n; j++)
      {
         if(i==j)min_cost[i][j] = min_road[i][j] = 0;
         else min_cost[i][j] = min_road[i][j] = MAX;
      }
   }
   for(int u = 1; u <= n; u++)
   {
      for(int i = first[u]; i != -1; i = e[i].next)
      {
         int v = e[i].v;
         int w = e[i].w;
         int l = e[i].l;
         min_cost[u][v] = w;
         min_road[u][v] = l;
      }
   }
   for(int k = 1; k <= n; k++)
   {
      for(int i = 1; i <= n; i++)
      {
         for(int j = 1; j <= n; j++)
         {
            if(min_cost[i][k]+min_cost[k][j] < min_cost[i][j])
            {
               min_cost[i][j] = min_cost[i][k]+min_cost[k][j];
            }
            if(min_road[i][j] > min_road[i][k]+min_road[k][j])
            {
               min_road[i][j] = min_road[i][k]+min_road[k][j];
            }
         }
      }
   }
}
void dfs(int u, int road, int cost)
{
   if(cost+min_cost[u][n]>k || road+min_road[u][n]>=best)return;
   if(u == n)
   {
      best = road;
      flag = true;
   }
   else
   {
      for(int i = first[u]; i != -1; i = e[i].next)
      {
         int v = e[i].v;
         int w = e[i].w;
         int l = e[i].l;
         if(!visit[v] && cost + w <= k && road+l < best)
         {
            visit[v] = true;
            dfs(v,road+l,cost+w);
            visit[v] = false;
         }
      }
   }
}
int main()
{
   int u,v,w,l;
   scanf("%d%d%d",&k,&n,&r);
   memset(first,-1,sizeof(first));
   t = -1;
   while(r--)
   {
      scanf("%d%d%d%d",&u,&v,&l,&w);
      add(u,v,l,w);
   }
   if(n==0)
   {
      printf("0\n");
      return 0;
   }
   floyd();
   flag = false;
   memset(visit,false,sizeof(visit));
   visit[1] = true;
   best = MAX;
   dfs(1,0,0);
   if(flag)printf("%d\n",best);
   else printf("-1\n");
   return 0;
}