/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

struct edge
{
    int u;
    ll w;

    bool operator < (const edge &e) const
    {
        return w > e.w;
    }
};

int n;
vector < edge > g1[maxn];
int used1[maxn];
ll d1[maxn];
void add_edge1(int v, int u, int w)
{
    g1[v].push_back({u, w});
    g1[u].push_back({v, w});
}

void dijkstra1(int s)
{
    for (int i = 1; i <= n; i ++)
        d1[i] = 1e18, used1[i] = 0;

    priority_queue < edge > q;
    d1[s] = 0;
    q.push({s, 0});

    while(!q.empty())
    {
        edge e = q.top();
        q.pop();
        if (!used1[e.u])
        {
            if (e.w <= d1[e.u])
            {
                int ver = e.u;
                for (int i = 0; i < g1[ver].size(); i ++)
                {
                    edge nb = g1[ver][i];
                    nb.w += e.w;
                    if (!used1[nb.u] && nb.w < d1[nb.u])
                    {
                        q.push(nb);
                        d1[nb.u] = nb.w;
                    }

                }
            }
        }
    }
}

vector < edge > g2[maxn];
int used2[maxn];
ll d2[maxn];
void add_edge2(int v, int u, int w)
{
    g2[v].push_back({u, w});
    g2[u].push_back({v, w});
}

void dijkstra2(int s)
{
    for (int i = 1; i <= n; i ++)
        d2[i] = 1e18, used2[i] = 0;

    priority_queue < edge > q;
    d2[s] = 0;
    q.push({s, 0});

    while(!q.empty())
    {
        edge e = q.top();
        q.pop();
        if (!used2[e.u])
            if (e.w <= d2[e.u])
            {
                int ver = e.u;
                for (int i = 0; i < g2[ver].size(); i ++)
                {
                    edge nb = g2[ver][i];
                    nb.w += e.w;
                    if (!used2[nb.u] && nb.w < d2[nb.u])
                    {
                        q.push(nb);
                        d2[nb.u] = nb.w;
                    }

                }
            }
    }
}

void solve()
{
    int m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        g1[i].clear(), g2[i].clear();
    for (int i = 1; i <= m; i ++)
    {
        int a, b, v, w;
        cin >> a >> b >> v >> w;
        add_edge1(a, b, v);
        add_edge2(a, b, w);
    }

    dijkstra1(1);
    dijkstra2(n);

    ll ans = 1e18;
    for (int i = 1; i <= n; i ++)
    {
        ans = min(ans, d1[i] + d2[i]);
    }

    cout << ans << endl;
}

int main()
{
    freopen("hurry.in", "r", stdin);
    freopen("hurry.out", "w", stdout);
    speed();
    int t;
    cin >> t;
    while(t --)
        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
*/