# include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6;
vector < pair <int, int> > g1[maxn],g2[maxn];
long long dist[maxn],dist2[maxn];
map <int,int> mp;
priority_queue <pair <long long,int> > q;
void dijkstra1(int v)
{
    int i;
    for(i=1;i<=v;i++)dist[i]=1e18;
    while(!q.empty())q.pop();
    q.push({0,v});
    dist[v] = 0;
    while(!q.empty())
    {
        int v = q.top().second;
        if(dist[v]!=-q.top().first){q.pop();continue;}
       // cout<<v<<"::"<<dist[v]<<endl;
        q.pop();
        for(auto u:g1[v])
        {
            if(dist[u.first]>dist[v]+u.second)
            {
                dist[u.first]=dist[v]+u.second;
                q.push({-dist[u.first],u.first});
            }

        }
    }
    return ;
}
void dijkstra2(int n)
{
    int v=  1;
    int i;
    while(!q.empty())q.pop();
    for(i=1;i<=n;i++)dist2[i]=1e18;
    q.push({0,v});
    dist2[v] = 0;
    while(!q.empty())
    {
        int v = q.top().second;
        if(dist2[v]!=-q.top().first){q.pop();continue;}
        q.pop();
        //cout<<v<<"->"<<dist2[v]<<endl;
        for(auto u:g2[v])
        {
            if(dist2[u.first]>dist2[v]+u.second)
            {
                dist2[u.first]=dist2[v]+u.second;
                q.push({-dist2[u.first],u.first});
            }
        }
    }
    return ;
}
void solve()
{
    int n,m;
    cin>>n>>m;
    int i,j,u,v,a,b;
    for(i=1;i<=n;i++){
    g1[i].clear();
    g2[i].clear();}
    for(i=1;i<=m;i++)
    {
        cin>>u>>v>>a>>b;
        g1[u].push_back({v,b});
        g1[v].push_back({u,b});
        g2[u].push_back({v,a});
        g2[v].push_back({u,a});
    }
    dijkstra1(n);
    dijkstra2(n);
    long long ans = 1e18;
    for(i=1;i<=n;i++)
    {
        //cout<<i<<" "<<dist[i]<<" "<<dist2[i]<<endl;
        ans = min(ans,dist[i]+dist2[i]);
    }
    cout<<ans<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
  freopen ("hurry.in","r",stdin); freopen ("hurry.out","w",stdout);
    int n,m;
    int i,j;
    int t;
    cin>>t;
    while(t--)solve();
}