#include <bits/stdc++.h>
#define fo(i,x,y) for (int i = x; i < y; i++)
#define fd(i,x,y) for(int i = x; i>= y; i--)
#define ll long long
#define clr(A,x) memset(A, x, sizeof A)
#define pb push_back
#define mod 1000000007
#define debug(x) cout <<#x << " = " << x << endl
using namespace std;
vector<int> lista[105];
int din,n;
int length[105][105];
int peaje[105][105];
bool used[105][10005];
int dp[105][10005];
const int MAXN=1e9;
int f(int padre,int dinero)
{
if(padre==n)
{
return 0;
}
if(used[padre][dinero])
{
return dp[padre][dinero];
}
int mini=MAXN;
fo(i,0,lista[padre].size())
{
int hijo=lista[padre][i];
if(dinero+peaje[padre][hijo]<=din)
{
mini=min(mini,f(hijo,dinero+peaje[padre][hijo])+length[padre][hijo]);
}
}
used[padre][dinero]=1;
dp[padre][dinero]=mini;
return mini;
}
int main()
{
cin.sync_with_stdio(false);
//freopen("D:\input.txt","r",stdin);
int t;
cin>>t;
fo(q,0,t)
{
memset(dp,0,sizeof(dp));
memset(used,0,sizeof(used));
fo(i,0,105)
{
lista[i].clear();
}
memset(length,1000000,sizeof(length));
memset(peaje,1000000,sizeof(peaje));
cin>>din>>n;
int r;
cin>>r;
fo(i,0,r)
{
int x,y,z,w;
cin>>x>>y>>z>>w;
lista[x].pb(y);
length[x][y]=min(length[x][y],z);
peaje[x][y]=min(peaje[x][y],w);
}
int ans=f(1,0);
if(ans==MAXN)
{
cout<<-1<<'\n';
}
else
{
cout<<ans<<'\n';
}
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgZm8oaSx4LHkpIGZvciAoaW50IGkgPSB4OyBpIDwgeTsgaSsrKQojZGVmaW5lIGZkKGkseCx5KSBmb3IoaW50IGkgPSB4OyBpPj0geTsgaS0tKQojZGVmaW5lIGxsIGxvbmcgbG9uZwojZGVmaW5lIGNscihBLHgpIG1lbXNldChBLCB4LCBzaXplb2YgQSkKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBtb2QgMTAwMDAwMDAwNwojZGVmaW5lIGRlYnVnKHgpIGNvdXQgPDwjeCA8PCAiID0gIiA8PCB4IDw8IGVuZGwKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnZlY3RvcjxpbnQ+IGxpc3RhWzEwNV07CmludCBkaW4sbjsKaW50IGxlbmd0aFsxMDVdWzEwNV07CmludCBwZWFqZVsxMDVdWzEwNV07CmJvb2wgdXNlZFsxMDVdWzEwMDA1XTsKaW50IGRwWzEwNV1bMTAwMDVdOwpjb25zdCBpbnQgTUFYTj0xZTk7CmludCBmKGludCBwYWRyZSxpbnQgZGluZXJvKQp7CiAgICBpZihwYWRyZT09bikKICAgIHsKICAgICAgICByZXR1cm4gMDsKICAgIH0KICAgIGlmKHVzZWRbcGFkcmVdW2RpbmVyb10pCiAgICB7CiAgICAgICAgcmV0dXJuIGRwW3BhZHJlXVtkaW5lcm9dOwogICAgfQogICAgaW50IG1pbmk9TUFYTjsKICAgIGZvKGksMCxsaXN0YVtwYWRyZV0uc2l6ZSgpKQogICAgewogICAgICAgIGludCBoaWpvPWxpc3RhW3BhZHJlXVtpXTsKICAgICAgICBpZihkaW5lcm8rcGVhamVbcGFkcmVdW2hpam9dPD1kaW4pCiAgICAgICAgewogICAgICAgICAgICBtaW5pPW1pbihtaW5pLGYoaGlqbyxkaW5lcm8rcGVhamVbcGFkcmVdW2hpam9dKStsZW5ndGhbcGFkcmVdW2hpam9dKTsKICAgICAgICB9CiAgICB9CiAgICB1c2VkW3BhZHJlXVtkaW5lcm9dPTE7CiAgICBkcFtwYWRyZV1bZGluZXJvXT1taW5pOwogICAgcmV0dXJuIG1pbmk7Cn0KaW50IG1haW4oKQp7CiAgICBjaW4uc3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIC8vZnJlb3BlbigiRDpcaW5wdXQudHh0IiwiciIsc3RkaW4pOwogICAgaW50IHQ7CiAgICBjaW4+PnQ7CiAgICBmbyhxLDAsdCkKICAgIHsKICAgICAgICBtZW1zZXQoZHAsMCxzaXplb2YoZHApKTsKICAgICAgICBtZW1zZXQodXNlZCwwLHNpemVvZih1c2VkKSk7CiAgICAgICAgZm8oaSwwLDEwNSkKICAgICAgICB7CiAgICAgICAgICAgIGxpc3RhW2ldLmNsZWFyKCk7CiAgICAgICAgfQogICAgICAgIG1lbXNldChsZW5ndGgsMTAwMDAwMCxzaXplb2YobGVuZ3RoKSk7CiAgICAgICAgbWVtc2V0KHBlYWplLDEwMDAwMDAsc2l6ZW9mKHBlYWplKSk7CiAgICAgICAgY2luPj5kaW4+Pm47CiAgICAgICAgaW50IHI7CiAgICAgICAgY2luPj5yOwogICAgICAgIGZvKGksMCxyKQogICAgICAgIHsKICAgICAgICAgICAgaW50IHgseSx6LHc7CiAgICAgICAgICAgIGNpbj4+eD4+eT4+ej4+dzsKICAgICAgICAgICAgbGlzdGFbeF0ucGIoeSk7CiAgICAgICAgICAgIGxlbmd0aFt4XVt5XT1taW4obGVuZ3RoW3hdW3ldLHopOwogICAgICAgICAgICBwZWFqZVt4XVt5XT1taW4ocGVhamVbeF1beV0sdyk7CiAgICAgICAgfQogICAgICAgIGludCBhbnM9ZigxLDApOwogICAgICAgIGlmKGFucz09TUFYTikKICAgICAgICB7CiAgICAgICAgICAgIGNvdXQ8PC0xPDwnXG4nOwogICAgICAgIH0KICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICBjb3V0PDxhbnM8PCdcbic7CiAgICAgICAgfQogICAgfQp9Cg==