#include<bits/stdc++.h>
using namespace std;

const int nmax=1e6+42;
const long long INF=1e18+42;

int n,m;

vector< pair<int,int> > adj[2][nmax];

void add(int u,int v,int a,int b)
{
    adj[0][u].push_back({v,a});
    adj[1][u].push_back({v,b});
}

priority_queue< pair<long long, pair<int,int> > > pq,idle;

long long dp[2][nmax];
bool been[2][nmax];

void note(long long cost,int node,int type)
{
    if(been[type][node])return;

    if(dp[type][node]>cost)
    {
        dp[type][node]=cost;
        pq.push({-cost,{node,type}});
    }
}
long long solve()
{
    scanf("%i%i",&n,&m);

    for(int i=1;i<=n;i++)
    {
        adj[0][i]={};
        adj[1][i]={};
    }

    for(int i=1;i<=m;i++)
    {
        int u,v,a,b;
        scanf("%i%i%i%i",&u,&v,&a,&b);

        add(u,v,a,b);
        add(v,u,a,b);
    }

    for(int i=1;i<=n;i++)
    {
        dp[0][i]=INF,dp[1][i]=INF;
        been[0][i]=0,been[1][i]=0;
    }

    pq=idle;
    pq.push({0,{1,0}});

    while(pq.size())
    {
        pair<long long, pair<int,int> > cur=pq.top();

        pq.pop();

        long long cost=-cur.first;
        int node=cur.second.first;
        int type=cur.second.second;

        if(been[type][node])continue;
        been[type][node]=1;

        if(type==0)
        {
            note(cost,node,1);
        }

        for(auto w:adj[type][node])
            note(cost+w.second,w.first,type);
    }

    return min(dp[0][n],dp[1][n]);
}

int main()
{
    freopen("hurry.in","r",stdin);
    freopen("hurry.out","w",stdout);

    int t;
    scanf("%i",&t);

    while(t)
    {
        t--;
        printf("%lld\n",solve());
    }

    return 0;
}
/*
3
5 6
1 2 2 1
2 3 3 5
3 4 9 3
1 3 6 6
2 5 7 6
3 5 8 1
5 5
1 2 1 1
2 3 2 2
3 5 1 4
4 5 2 5
1 4 3 4
5 7
1 2 6 2
1 3 3 4
1 4 4 5
2 3 5 2
2 4 3 1
2 5 7 4
4 5 3 2


6
4
5
*/