#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int INF=999999999;
int money,n,m,id;

struct SPFA
{
	int cost,dop,dis;
};

struct edge
{
	int v,d,w,nx;
}set[20005];
int head[1005],dist[1005];
bool vis[1005];

priority_queue<SPFA> Q;

bool operator<(const SPFA &a,const SPFA &b)
{
	return a.dis>b.dis;
}

void Addedge(int u,int v,int d,int w)
{
	id++;set[id].v=v;set[id].d=d;set[id].w=w;set[id].nx=head[u];
	head[u]=id;
}

void init()
{
	int u,v,d,w;
	scanf("%d%d%d",&money,&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d%d",&u,&v,&d,&w);
		Addedge(u,v,d,w);
	}
}

void spfa()
{
	for(int i=1;i<=n;i++)dist[i]=INF;
	struct SPFA top,tmp;
	tmp.dop=1;tmp.cost=0;tmp.dis=0;
	Q.push(tmp);dist[1]=0;
	while(!Q.empty())
	{
		top=Q.top();Q.pop();
		if(top.dop==n)return ;
		for(int k=head[top.dop];k>0;k=set[k].nx)
		{
			if(top.cost+set[k].w<=money)
			{
				if(top.dis+set[k].d<dist[set[k].v])dist[set[k].v]=top.dis+set[k].d;
				tmp.cost=top.cost+set[k].w;tmp.dis=top.dis+set[k].d;tmp.dop=set[k].v;
				Q.push(tmp);vis[set[k].v]=1;
			}
		}
	}
}

int main()
{
	/*freopen("poj.in","r",stdin);
	freopen("poj.out","w",stdout);*/
	init();
	spfa();
	if(dist[n]>=INF)printf("-1\n");
	else printf("%d\n",dist[n]);
	//fclose(stdin); fclose(stdout);
	return 0;
}