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