#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
ll i,j,p,n,m,k,t,p1,ans;
struct Put
{
    ll v,d;
};
bool operator<(Put a,Put b)
{
    return a.d>b.d;
}
bool b[100006];
priority_queue <Put> q;
vector <Put> v[100006],g[100006];
ll r[100006];
void read()
{
    freopen("hurry.in","r",stdin);
    freopen("hurry.out","w",stdout);
}
void solve()
{
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        v[i].clear();
        g[i].clear();
        r[i]=LLONG_MAX;
    }
    for(i=1; i<=m; i++)
    {
        cin>>p>>j>>k>>p1;
        v[p].push_back({j,k});
        v[j].push_back({p,k});
        g[p].push_back({j,p1});
        g[j].push_back({p,p1});
    }
    q.push({n,0});
    fill(b+1,b+n+1,0);
    ans=LLONG_MAX;
    while(!q.empty())
    {
        auto i=q.top();
        q.pop();
        if(!b[i.v])
        {
           // cout<<i.v<<"  r[i]  "<<i.d<<endl;
            b[i.v]=1;
            r[i.v]=i.d;
            for(auto p:g[i.v])
            {
                if(!b[p.v])
                {
                    q.push({p.v,p.d+i.d});
                }
            }
        }
    }/**
    for(i=1; i<=n; i++)
        cout<<r[i]<<" ";*/
    q.push({1,0});
    fill(b+1,b+n+1,0);
    while(!q.empty())
    {
        auto i=q.top();
        q.pop();
        if(!b[i.v])
        {
            //cout<<i.v<<" "<<i.d<<" "<<r[i.v]<<endl;
            b[i.v]=1;
            ans=min(ans,r[i.v]+i.d);
            for(auto p:v[i.v])
            {
                if(!b[p.v])
                {
                    q.push({p.v,p.d+i.d});
                }
            }
        }
    }
    //ans=min(ans,r[1]);
    cout<<ans<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    read();
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}