#include<iostream>
#include<vector>
#include<queue>
#include<tuple>
using namespace std;

const int MAXN=1e5;
const long long INF=1e18;

vector<pair<int, int> > gcar[MAXN], gbike[MAXN];
long long dcar[MAXN], dbike[MAXN];
bool v[MAXN];

void GetDistCar(int n, int s)
{
    for(int i=0; i<n; i++)
    {
        v[i]=false, dcar[i]=INF;
    }

    dcar[s]=0;
    priority_queue<pair<long long, int> > q;
    q.push({0, s});

    while(!q.empty())
    {
        int idx;
        long long x;
        tie(x, idx)=q.top();
        q.pop();
        x*=-1;

        if(v[idx])
        {
            continue;
        }

        v[idx]=true;
        dcar[idx]=x;

        for(pair<int, int> p:gcar[idx])
        {
            int node;
            long long u;
            tie(node, u)=p;

            q.push({-u-x, node});
        }
    }

    return;
}

void GetDistBike(int n, int s)
{
    for(int i=0; i<n; i++)
    {
        v[i]=false, dbike[i]=INF;
    }

    dbike[s]=0;
    priority_queue<pair<long long, int> > q;
    q.push({0, s});

    while(!q.empty())
    {
        int idx;
        long long x;
        tie(x, idx)=q.top();
        q.pop();
        x*=-1;

        if(v[idx])
        {
            continue;
        }

        v[idx]=true;
        dbike[idx]=x;

        for(pair<int, int> p:gbike[idx])
        {
            int node;
            long long u;
            tie(node, u)=p;

            q.push({-u-x, node});
        }
    }

    return;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

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

    int t;
    cin >> t;

    while(t--)
    {
        int n, m;
        cin >> n >> m;

        for(int i=0; i<m; i++)
        {
            int a, b, x, y;
            cin >> a >> b >> x >> y;
            a--, b--;

            gcar[a].push_back({b, x});
            gcar[b].push_back({a, x});
            gbike[a].push_back({b, y});
            gbike[b].push_back({a, y});
        }

        GetDistCar(n, 0);
        GetDistBike(n, n-1);

        long long ans=INF;
        for(int i=0; i<n; i++)
        {
            ans=min(ans, dcar[i]+dbike[i]);
        }

        cout << ans << "\n";

        for(int i=0; i<n; i++)
        {
            gcar[i].clear(), gbike[i].clear();
        }
    }

    return 0;
}
/*
1
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
*/