#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=2e5+10;
const int M=3e5+10;
int h[N],ne[M],e[M],w[M],w1[M],w2[M],idx;
void add(int a,int b,int c,int d,int id)
{
w[idx]=c,w1[idx]=d,w2[idx]=id,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int n,m;
int vis[M];
struct node
{
int a,b,c,d;
};
node pi[M],qi[M];
int cnt;
int dist[N],st[N];
void dis()
{
for(int i=1;i<=n;i++)
{
dist[i]=0x3f3f3f3f;
st[i]=0;
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> si;
si.push({0,1});
dist[1]=0;
while(si.size())
{
auto t=si.top();
si.pop();
int ver=t.second,distance=t.first;
if(st[ver])continue;
st[ver]=1;
for(int i=h[ver];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>dist[ver]+w[i])
{
dist[j]=dist[ver]+w[i];
si.push({dist[j],j});
}
}
}
cnt=0;
for(int i=1;i<=n;i++)
{
for(int j=h[i];j!=-1;j=ne[j])
{
int k=e[j];
if(dist[k]==dist[i]+w[j])
{
qi[++cnt]=pi[w2[j]];
}
}
}
for(int i=1;i<=n;i++)h[i]=-1;
idx=0;
for(int i=1;i<=cnt;i++)
{
int a=qi[i].a,b=qi[i].b,c=qi[i].c,d=qi[i].d;
add(a,b,c,d,1);
}
cout << dist[n]<<" ";
}
int dfn[N],low[N],tim;
int ty[N];
stack<int> si;
int scc,sccnt[N],id[N];
void tarjan(int u)
{
dfn[u]=low[u]=++tim;
si.push(u);
ty[u]=1;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(dfn[j]==0)
{
tarjan(j);
low[u]=min(low[u],low[j]);
}
else if(ty[j]) low[u]=min(low[u],dfn[j]);
}
if(low[u]==dfn[u])
{
scc++;
int j;
do
{
j=si.top();
si.pop();
ty[j]=0;
id[j]=scc;
}while(j!=u);
}
}
int di[N];
void top()
{
queue<int> fi;
for(int i=1;i<=scc;i++)
{
dist[i]=-0x3f3f3f3f;
}
for(int i=1;i<=scc;i++)
{
if(di[i]==0)
{
fi.push(i);
dist[i]=sccnt[i];
}
}
while(fi.size())
{
auto t=fi.front();
fi.pop();
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
di[j]--;
dist[j]=max(dist[j],dist[t]+w1[i]+sccnt[j]);
if(di[j]==0) fi.push(j);
}
}
}
void slove()
{
cin >> n>>m;
for(int i=1;i<=n;i++) h[i]=-1;
idx=0;
for(int i=1;i<=m;i++)
{
int a,b,c,d;
cin >> a>>b>>c>>d;
add(a,b,c,d,i);
pi[i]={a,b,c,d};
}
dis();
for(int i=1;i<=n;i++)
{
if(!dfn[i])tarjan(i);
}
for(int i=1;i<=scc;i++)h[i]=-1;
idx=0;
for(int i=1;i<=scc;i++) di[i]=0;
for(int i=1;i<=cnt;i++)
{
int a=qi[i].a,b=qi[i].b,c=qi[i].c,d=qi[i].d;
if(id[a]==id[b])
{
sccnt[id[a]]+=d;
}
else
{
add(id[a],id[b],c,d,0);
di[id[b]]++;
}
}
top();
cout << dist[id[n]]<<endl;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int t;
cin >> t;
while(t--)
{
slove();
}
return 0;
}