include
include
include
include
include
include
include
include
include
include
include
include
include
using namespace std;
define open freopen("input.txt","r",stdin)
define close freopen ("output.txt","w",stdout)
define db double
define ll long long
define lll unsigned long long
define loop(i,a,n) for(int i=a;i<=n;i++)
define sf scanf
define sf1(a) sf("%d",&a)
define sf2(a,b) sf("%d %d",&a,&b)
define sf3(a,b,c) sf("%d %d %d",&a,&b,&c)
define sf4(a,b,c,d) sf("%d %d %d %d",&a,&b,&c,&d)
define sfd(a) sf("%lf",&a)
define sfd2(a,b) sf("%lf %lf",&a,&b)
define sfl1(a) sf("%lld",&a)
define sfl2(a,b) sf("%lld %lld",&a,&b)
define pii pair
define pll pair
define pf printf
define pfi(x) pf("%d",x)
define pfl(x) pf("%lld",x)
define NL puts("")
define bug pf("here is bug\n")
define pft(tc) printf("Case %d:",tc++)
define PI (2.0*acos(0.0))
//#define PI acos(-1.0)
define mem(a,v) memset(a,v,sizeof a)
define endl '\n'
define pb push_back
define xx first
define yy second
define mp make_pair
define all(a) a.begin(),a.end()
template inline T bigmod(T p,T e,T M)
{
ll ret = 1;
for(; e > 0; e >>= 1)
{
if(e & 1) ret = (ret * p) % M;
p = (p * p) % M;
}
return (T)ret;
}
template inline T gcd(T a,T b)
{
if(b==0)return a;
return gcd(b,a%b);
}
template inline T lcm(T a,T b)
{
return (a/gcd(a,b))*b;
}
template inline T modinverse(T a,T M)
{
return bigmod(a,M-2,M);
} // M is prime}
template inline T bpow(T p,T e)
{
ll ret = 1;
for(; e > 0; e >>= 1)
{
if(e & 1) ret = (ret * p);
p = (p * p);
}
return (T)ret;
}
//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
//int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
//int dx[]={0,1,0,-1};int dy[]={1,0,-1,0}; //4 Direction
define linf 3000000000000000000ll
define inf 999999999
define MX 1000000
define mod (ll) 1000000007
define eps 1e-6
define ub upper_bound // return the right most index of x<val
define lb lower_bound // return the right most index of x<=val
struct data
{
int el1,el2,el3;
data() {}
data(int a,int b,int c)
{
el1=a,el2=b,el3=c;
}
bool friend operator<(data a,data b)
{
return a.el2> b.el2;// sort decreasingly but increasingly for priority_queue
}
};
struct node{
int from,to,c,l,next;
node(){}
node(int a,int b,int _c,int _d,int e){
from=a,to=b,c=_c,l=_d,next=e;
}
};
node edge[10004];
int n,m,k;
ll N,M,K;
int head[10004];
int ans=inf;
priority_queue pq;
int cc=0;
void diax(int y){
while(!pq.empty()) pq.pop();
ans=inf;
pq.push(data(y,0,0));
while(!pq.empty()){
data x=pq.top();
pq.pop();
int from=x.el1;
int cst=x.el2;
int len=x.el3;
if(from==n){
ans=len;
break;
}
//pf("%d %d %d\n",from,cst,len);
for(int i=head[from];i!=-1;i=edge[i].next){
int to=edge[i].to;
int c=edge[i].c;
int l=edge[i].l;
//pf("s %d %d %d\n",to,c,l);
//pf("pp %d %d %d\n",cost[from],dis[from],dis[to]);
if(c+cst<=k){
int x1=l+len;
int x2=c+cst;
//pf("%d %d\n",dis[to],cost[to]);
pq.push(data(to,x2,x1));
}
}
}
}
int main()
{
int t,tc=1;
sf1(t);
while(t--){
mem(head,-1);
sf3(k,n,m);
cc=0;
for(int i=1;i<=m;i++){
int s,d,l,c;
sf3(s,d,l);
sf1(c);
edge[cc]=node(s,d,c,l,head[s]);
head[s]=cc++;
}
if(k==0){
pf("-1\n");
continue;
}
diax(1);
if(ans==inf){
pf("-1");
}
else{
pf("%d\n",ans);
}
}
return 0;
}
/*
*/indent preformatted text by 4 spaces