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

ifstream fin("hurry.in");
ofstream fout("hurry.out");

const int maxn = 1e5+2;
int t, n, m, d1[maxn], d2[maxn];
bool used[maxn];

struct edge1
{
    int ver;
    int a;
    bool operator<(const edge1&e)const
    {
        return (a > e.a);
    }
};

struct edge2
{
    int ver;
    int b;
    bool operator<(const edge2&e)const
    {
        return (b > e.b);
    }
};

//vector<edge1> v1[maxn];
//vector<edge2> v2[maxn];

void Dijkstra1(int s, vector<edge1> v1[], vector<edge2> v2[])
{
    memset(d1, -1, sizeof(d1));
    d1[s] = 0;
    memset(used, 0, sizeof(used));
    priority_queue<edge1> q;
    edge1 e={s,0}; q.push(e);

    while (!q.empty())
    {
        e.ver = q.top().ver;  e.a = q.top().a;  q.pop();
        //fout << "*" << e.ver << " " << e.a << '\n' ;
        if (d1[e.ver]==-1 || e.a <= d1[e.ver])
        {
            if (!used[e.ver])
            {
                used[e.ver] = 1;
                int sz = v1[e.ver].size(), i;
                for (i=0; i<sz; ++i)
                {
                    edge1 nb;  nb.ver = v1[e.ver][i].ver;  nb.a = v1[e.ver][i].a;
                    if (d1[nb.ver]==-1 || e.a+nb.a < d1[nb.ver])
                    {
                        nb.a += e.a;
                        d1[nb.ver] = nb.a;
                        q.push(nb);
                    }
                }
            }
        }
    }
}

void Dijkstra2(int s, vector <edge1> v1[], vector <edge2> v2[])
{
    memset(d2, -1, sizeof(d2));
    d2[s] = 0;
    memset(used, 0, sizeof(used));
    priority_queue<edge2> q;
    edge2 e={s,0}; q.push(e);

    while (!q.empty())
    {
        e.ver = q.top().ver;  e.b = q.top().b;  q.pop();
        if (d2[e.ver]==-1 || e.b <= d2[e.ver])
        {
            if (!used[e.ver])
            {
                used[e.ver] = 1;
                int sz = v2[e.ver].size(), i;
                for (i=0; i<sz; ++i)
                {
                    edge2 nb;  nb.ver = v2[e.ver][i].ver;  nb.b = v2[e.ver][i].b;
                    if (d2[nb.ver]==-1 || e.b+nb.b < d2[nb.ver])
                    {
                        nb.b += e.b;
                        d2[nb.ver] = nb.b;
                        q.push(nb);
                    }
                }
            }
        }
    }
}

/*void print()
{
    int i, j, len;
    for (i=1; i<=n; ++i)
    {
        len = v1[i].size();
        fout << i << ": " ;
        for (j=0; j<len; ++j) fout << v1[i][j].ver << "-" << v1[i][j].a << " " ;
        fout << '\n' ;
    }

    for (i=1; i<=n; ++i)
    {
        len = v2[i].size();
        fout << i << ": " ;
        for (j=0; j<len; ++j) fout << v2[i][j].ver << "-" << v2[i][j].b << " " ;
        fout << '\n' ;
    }
}*/

void solve(vector <edge1> v1[], vector <edge2> v2[])
{
    //print();
    Dijkstra1(1, v1, v2);
    int i, minp = d1[n];
    for (i=1; i<n; ++i)
    {
        Dijkstra2(i, v1, v2);
        if (d1[i]!=-1 && d2[n]!=-1 && d1[i]+d2[n] < minp) minp = d1[i]+d2[n];
    }
    fout << minp << '\n' ;

    /*for (i=1; i<=n; ++i)
    {
        v1[i].clear();
        v2[i].clear();
    }*/
}

void read()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    fin >> t ;
    int l, i, x, y, a, b;
    for (l=1; l<=t; ++l)
    {
        fin >> n >> m ;
        vector<edge1> v1[maxn];
        vector<edge2> v2[maxn];
        for (i=1; i<=m; ++i)
        {
            fin >> x >> y >> a >> b ;
            v1[x].push_back({y,a});
            v1[y].push_back({x,a});
            v2[x].push_back({y,b});
            v2[y].push_back({x,b});
        }
        solve(v1, v2);
    }
}

int main()
{
    read();
    return 0;
}