#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;
//英语 看博友分析 抄博友程序 dfs 巧妙 背
struct nod{
int des;
int len;
int toll;
int id;
};
int vis[10008];
int dp[108][10008];//走到城市i 时总过路费为j 的条件下，最优路径的长度
int k;
int n;
int m;
int jg=-1;
vector<nod> ve[150];
void dfs(int x,int L,int T)
{
if(dp[x][T]>=L)//抄博友程序 巧妙
{
dp[x][T]=L;
}else
{
return;
}
//cout<<x<<" "<<L<<" "<<T<<endl;
if(T>k)
{
//cout<<"end"<<endl;
return ;
}
if(L>jg && jg!=-1)
{
//cout<<"end"<<endl;
return;
}
if(x==n)
{
if(L<jg || jg==-1)
{
jg=L;
}
//cout<<"end"<<endl;
return;
}
for(int i=0;i<ve[x].size();i++)
{
int y=ve[x][i].des;
int l=ve[x][i].len;
int t=ve[x][i].toll;
int h=ve[x][i].id;
if(vis[h]==0)
{
vis[h]=1;
dfs(y,L+l,T+t);
vis[h]=0;
}
}
//cout<<"end"<<endl;
return;
}
int main()
{
//cin>>k>>n>>m;
memset(dp,0x3f,sizeof(dp));
scanf("%d%d%d",&k,&n,&m);
for(int i=0;i<m;i++)
{
int so;
nod t;
//cin>>so>>t.des>>t.len>>t.toll;
scanf("%d%d%d%d",&so,&t.des,&t.len,&t.toll);
t.id=i;
ve[so].push_back(t);
}
dfs(1,0,0);//
cout<<jg<<endl;
return 0;
}
