#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;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgZW5kbCAnXG4nCiNkZWZpbmUgSU5GIDFlOQppbnQgbixkcFsxMDAwNV1bMTA1XTsKaW50IHNvbHZlKGludCByZW0saW50IGksdmVjdG9yPCB2ZWN0b3I8IHBhaXI8IGludCxwYWlyPGludCxpbnQ+ID4gPiA+ICZ2KQp7CglpZihpPT0obi0xKSkKCXsKCQlyZXR1cm4gMDsKCX0KCWlmKGRwW3JlbV1baV0gIT0tMSkKCQlyZXR1cm4gZHBbcmVtXVtpXTsKCWludCBhbnM9SU5GOwoJZm9yKGludCBqPTA7ajx2W2ldLnNpemUoKTtqKyspCgl7CgkJaWYocmVtPj12W2ldW2pdLnNlY29uZC5maXJzdCkKCQkJYW5zID0gbWluKGFucyxzb2x2ZShyZW0tdltpXVtqXS5zZWNvbmQuc2Vjb25kLHZbaV1bal0uZmlyc3QsdikrdltpXVtqXS5zZWNvbmQuZmlyc3QpOwoJfQoJZHBbcmVtXVtpXT1hbnM7CglyZXR1cm4gYW5zOwp9CmludCBtYWluKCkKewogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4udGllKE5VTEwpOwogICAgaW50IHQ7CiAgICBjaW4+PnQ7CiAgICB3aGlsZSh0LS0pCiAgICB7CiAgICAJbWVtc2V0KGRwLC0xLHNpemVvZihkcCkpOwoJCWludCBrLHI7CgkJY2luPj5rPj5uPj5yOwoJCXZlY3RvcjwgdmVjdG9yPCBwYWlyPCBpbnQscGFpcjxpbnQsaW50PiA+ID4gPnYobik7CgkJd2hpbGUoci0tKQoJCXsKCQkJaW50IHMsZCxsLHRvbDsKCQkJY2luPj5zPj5kPj5sPj50b2w7CgkJCXMtLTsKCQkJZC0tOwoJCQl2W3NdLnB1c2hfYmFjayhtYWtlX3BhaXIoZCxtYWtlX3BhaXIobCx0b2wpKSk7CgkJfQoJCWludCByZXM9c29sdmUoaywwLHYpOwoJCWlmKHJlcz09SU5GKQoJCWNvdXQ8PC0xPDxlbmRsOwoJCWVsc2UKCQljb3V0PDxyZXM8PGVuZGw7CiAgICB9CiAgICByZXR1cm4gMDsKfQo=

Mgo1CjYKNwoxIDIgMiAzCjIgNCAzIDMKMyA0IDIgNAoxIDMgNCAxCjQgNiAyIDEKMyA1IDIgMAo1IDQgMyAyCjAKNAo0CjEgNCA1IDIKMSAyIDEgMAoyIDMgMSAxCjMgNCAxIDA=

2
5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2
0
4
4
1 4 5 2
1 2 1 0
2 3 1 1
3 4 1 0