include<iostream>

include<vector>

include<cstring> //与memset相关

using namespace std;

int k,N,R; //钱数 城市数 道路数

struct Road

{

   intd,L,t;   //终点  长度  过路费   起点以下标表示

} ;

vector<vector<struct Road>> G(110); //G数组有110行 每一行都是一个road数组

int minLen; //最短路径

int totalLen; //总路径

int totalCost; //总花费

int visited[110] ; //记录一个城市是否走过

void dfs(int s)

{

   if(s== N)

   {

          totalLen= min(minLen,totalLen);

          return;

   }

   for(inti = 0;i < G[s].size();i++)

   {

          Roadr = G[s][i];

          if(totalCost+ r.t > k)

          continue;

          if(!visited[r.d])

          {

                 totalLen+= r.L;

                 totalCost+= r.t ;

                 visited[r.d]= 1;

                 dfs(r.d);

                 visited[r.d]= 0;

                 totalLen-= r.L;

                 totalCost-= r.t;

          }

   }

}

int main()

{

   cin>> k >> N >> R;

   for(inti = 0;i < R;i++)

   {

          ints;

          Roadr;

          cin>> s >> r.d >> r.L >> r.t ;

   if(s!=r.d)

          {

                 G[s].push_back(r);

          }

   }

   memset(visited,0,sizeof(visited));

   totalLen= 0;

   minLen= 1 << 30;

   totalCost= 0;

   visited[1]= 1;

   dfs(1);

   if(minLen< (1 << 30))

   {

          cout<< minLen <<endl;

   }

   else

          cout<< "-1" << endl;

   return0;

}