#include <iostream>
#include <cstring>
#define inf 0x3f3f3f3f//定义inf为无穷大using namespace std;int n,idx,k,r,sum;
const int N=1e4+5;
int h[N],vis[N];struct node
{int u,v,w,cost;//分别用来存储原城市，目的城市，路径长度，所消耗的硬币int next;//用来存边
}arr[N];void add(int u,int v,int w,int cost)//用链式向前星存图
{arr[idx].v=v;arr[idx].w=w;arr[idx].cost=cost;arr[idx].next=h[u];h[u]=idx++;}void dfs(int x,int step,int cost)
{if(cost>k||step>sum)//如果消耗的硬币超过所拥有的，或者此时的路径已经大于最短路径，那么这种情况就不可取{return;}if(x==n){sum=min(sum,step);//保证结果是最短的路径}for(int i=h[x];i!=-1;i=arr[i].next)//链式向前星的遍历方式{int vv=arr[i].v;if(!vis[vv]){vis[vv]=1;dfs(vv,step+arr[i].w,cost+arr[i].cost);vis[vv]=0;}}
}int main()
{int a,b,c,d;memset(h,-1,sizeof h);//把h数组赋值为-1（为什么的话——详见链式向前星）cin >> k >> n >> r;for(int i=1;i<=r;i++){cin >> a >> b >> c >> d;add(a,b,c,d);}sum=inf;dfs(1,0,0);if(sum==inf) cout << "-1" << endl;else cout << sum << endl;return 0;
}