#include<bits/stdc++.h>
#define INF 2e9
using namespace std;
struct node
{
    long long vr,tg;
    node(){}
    node(long long a, long long b)
    {
        vr=a;
        tg=b;
    }
};
priority_queue <node> pq;
bool operator<(node a,node b)
{
    return a.tg > b.tg;
}
long long used[300500];
long long dist[300500];
long long n;
vector <node> g[300500];
void dijkstra(long long vr)
{

    for(long long i=1; i<=2*n; i++)
        dist[i]=INF;
    pq.push( node ( vr, 0 ) );
    dist[vr]=0;
    while(!pq.empty())
    {

        vr=pq.top().vr;
        pq.pop();
        //cout<<vr<<endl;
        /*for(long long i=0;i<=10;i++)
        {
            cout<<dist[i]<<" ";
        }*/
        if(used[vr])
            continue;
        used[vr]=1;
        for(long long i=0; i<g[vr].size(); i++)
        {
            long long sb=dist[vr]+g[vr][i].tg;

            if(!used[g[vr][i].vr]&&sb<dist[g[vr][i].vr])
            {
                 ///cout<<g[vr][i].vr<<" "<<sb<<endl;
                 pq.push(node (g[vr][i].vr,sb));
                dist[g[vr][i].vr]=sb;
            }
        }
    }
}
void solve()
{
    long long m;
    cin>>n>>m;
    for(long long i=0;i<m;i++)
    {
        long long a,b,c,d;
        cin>>a>>b>>c>>d;
        g[a].push_back({b,c});
        g[a].push_back({n+b,d});
        g[n+a].push_back({n+b,d});
        g[b].push_back({a,c});
        g[n+b].push_back({a,d});
        g[n+b].push_back({n+a,d});
    }
    dijkstra(1);
    //cout<<endl;
    cout<<min(dist[n],dist[2*n])<<endl;
    //cout<<dist[2*n]<<endl;
    for(long long i=0;i<=2*n;i++)
    {
        used[i]=0;
        g[i].clear();
    }
}
int main()
{
    freopen("hurry.in", "r", stdin);
    freopen("hurry.out", "w", stdout);

    long long t;
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}