> #include<iostream>
> #include<cstdlib>
> #include<cstdio>
> #include<vector>
> #include<queue>
> #include<cstring>
> using namespace std;
> struct po
> {
> 	int shu,dist,qian;
> 	bool operator < (const po&other) const{
> 		return dist>other.dist;
> 	}
> };
> struct pp
> {
> 	int shu,quan,qian;
> };
> int meiyong[1];
> vector<pp>ve[10005];
> priority_queue<po>Q;
> bool vist[20005];
> int dis[20005];
> int qian[20005];
> int main()
> {
> 	//freopen("heap.in","r",stdin);
> 	//freopen("heap.out","w",stdout);
> 	int n,e,i,j,t;
> 	pp go;
> 	memset(meiyong,127,sizeof(meiyong));
> 	cin>>t>>n>>e;
> 	for(i=1;i<=e;i++)
>     {
> 		int x,y,q,l;
> 		cin>>x>>y>>q>>l;
> 		go.shu=y;
> 		go.quan=q;
> 		go.qian=l;
> 		ve[x].push_back(go);
> 	}
> 	/*for(i=1;i<=n;i++)
> 	{
> 		for(j=0;j<ve[i].size();j++)
> 			cout<<ve[i][j].shu<<" ";
> 		cout<<endl;
> 	}
> 	for(i=1;i<=n;i++)
> 	{
> 		for(j=0;j<ve[i].size();j++)
> 			cout<<ve[i][j].qian<<" ";
> 		cout<<endl;
> 	}*/
> 	po ls;
> 	ls.shu=1;
> 	ls.dist=0;
> 	ls.qian=t;
> 	Q.push(ls);
> 	//cout<<meiyong[0]<<endl;
> 	/*for(i=2;i<=n;i++)
> 	{
> 		ls.shu=i;
> 		ls.dist=meiyong[0];
> 		Q.push(ls);
> 	}*/
> 	i=0;
> 	while(i!=2*n)
> 	{
> 		if(Q.empty())
> 		    break;
> 		//if(i==5)
> 		//    int jieyong=0;
> 		int dds=Q.top().shu,ddd=Q.top().dist,ddq=Q.top().qian;
> 		if(ddq<0)
> 		{
> 			Q.pop();
> 			continue;
> 		}
> 		//cout<<dds<<" "<<ddd<<" "<<ddq<<endl;
> 		for(j=0;j<ve[dds].size();j++)
> 		{
> 			if(!vist[ve[dds][j].shu])
> 			{
> 				ls.shu=ve[dds][j].shu;
> 				ls.dist=ddd+ve[dds][j].quan;
> 				ls.qian=ddq-ve[dds][j].qian;
> 				Q.push(ls);
> 			}
> 		}
> 		int tt;
> 		//cout<<"*****"<<Q.top().shu<<"*****"<<endl;
> 		tt=Q.top().qian;
> 		if(tt<0)
> 		{
> 			Q.pop();
> 			continue;
> 		}
> 		//t=tt;
> 		i++;
> 		if(!vist[Q.top().shu])
> 		{
> 			vist[Q.top().shu]=1;
> 			dis[Q.top().shu]=Q.top().dist;
> 		}
> 		if(vist[n])
> 		    break;
> 		Q.pop();
> 	}
> 	if(vist[n])
> 	    cout<<dis[n];
> 	else cout<<"-1";
> 	return 0;
> }