#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define INF 1e9
int n,dp[10005][105];
int solve(int rem,int i,vector< vector< pair< int,pair<int,int> > > > &v)
{
	if(i==(n-1))
	{
		return 0;
	}
	if(dp[rem][i] !=-1)
		return dp[rem][i];
	int ans=INF;
	for(int j=0;j<v[i].size();j++)
	{
		if(rem>=v[i][j].second.first)
			ans = min(ans,solve(rem-v[i][j].second.second,v[i][j].first,v)+v[i][j].second.first);
	}
	dp[rem][i]=ans;
	return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
    	memset(dp,-1,sizeof(dp));
		int k,r;
		cin>>k>>n>>r;
		vector< vector< pair< int,pair<int,int> > > >v(n);
		while(r--)
		{
			int s,d,l,tol;
			cin>>s>>d>>l>>tol;
			s--;
			d--;
			v[s].push_back(make_pair(d,make_pair(l,tol)));
		}
		int res=solve(k,0,v);
		if(res==INF)
		cout<<-1<<endl;
		else
		cout<<res<<endl;
    }
    return 0;
}