#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5+10, maxm = 5e3+10, inf = 1e15;
 
int n, m, t;
int a[maxn][2];
bool used[maxn][2];
ifstream fin("hurry.in");
ofstream fout("hurry.out");

struct edge {

    int to, c[2];
    edge(){}
    edge(int _to, int _c, int _b) {

        to = _to;
        c[0] = _c;
        c[1] = _b;

    }

};

struct element {

    int dist;
    int node;
    bool bl;

    element(){}
    element(int _dist, int _node, bool _bl) {

        dist = _dist;
        node = _node;
        bl = _bl;

    }

    inline friend bool operator < (element a, element b) {

        return a.dist > b.dist;

    }

};

vector < edge > v[maxn];
priority_queue < element > pq;

void dijkstra() {

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

    while (!pq.empty()) {

        auto [dist, x, bl] = pq.top();
        pq.pop();
        if (used[x][bl]) continue;
        used[x][bl] = 1;
        if (!bl) pq.push({dist, x, 1});

        for (edge e : v[x]) {

            if (a[e.to][bl] > dist + e.c[bl]) {

                a[e.to][bl] = dist + e.c[bl];
                pq.push({a[e.to][bl], e.to, bl});

            }

        }


    }

}

void solve() {

    dijkstra();
    fout << min(a[n][0], a[n][1]) << '\n';    

}

void fast_io() {
 
    ios_base :: sync_with_stdio(0);
    fin.tie(nullptr);
    fout.tie(nullptr);
    cerr.tie(nullptr);
 
}
 
void reset() {

    for (int i = 1 ; i <= n ; ++i) {

        v[i].clear();
        used[i][0] = used[i][1] = 0;
        a[i][0] = a[i][1] = inf;

    }

}

void read() {
 
    int x, y, c, b;
    fin >> n >> m;

    for (int i = 1 ; i <= m ; ++i) {

        fin >> x >> y >> c >> b;
        v[x].push_back({y, c, b});
        v[y].push_back({x, c, b});

    }
     
 
}
 
signed main () {

    for (int i = 0 ; i < maxn ; ++i)
        a[i][0] = a[i][1] = inf;
 
    fast_io();
    
    fin >> t;
    while (t--) {
        
        reset();
        read();
        solve();
    
    }
 
    return 0;
 
}