#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define LL long long int
#define ULL unsigned LL
#define LD long double
#define FI first
#define SE second
#define PB push_back
#define PF push_front
#define V vector
#define PQ priority_queue
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define FORI(i, a, b) for(int i = a; i < b ; ++i)
#define FORD(i, a, b) for(int i = a; i > b ; --i)

using namespace std;
using pii = pair<int, int>;

const LL INF = 1e18;

struct Edge {
    int from, to, dist[2];
};

int main(){
    ifstream cin("hurry.in");
    ofstream cout("hurry.out");
//    ios_base::sync_with_stdio(false);
//    cin.tie(NULL);
//    cout.tie(NULL);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    clock_t start_t = clock();

    int t, n, m, u, v, a, b;
    cin >> t;
    FORI(ti,0,t){
        cin >> n >> m;
        V<V<Edge>> edg(n);
        FORI(i,0,m){
            cin >> u >> v >> a >> b;
            --u; --v;
            edg[u].push_back({u, v, {b, a}});
            edg[v].push_back({v, u, {b, a}});
        }

        V<V<LL>> d(2, V<LL> (n, INF));
        d[0][0] = d[1][0] = 0;
        PQ<pair<LL, int>> q;
        q.push({0, 0});
        while (!q.empty()){
            LL cur_d = -q.top().first;
            int v = q.top().second;
            q.pop();

            FORI(k_from,0,2){
                if (cur_d > d[k_from][v])  continue;
                FORI(k_to,0,k_from+1){
                    FORI(j,0,edg[v].size()){
                        int to = edg[v][j].to, len = edg[v][j].dist[k_to];
                        if (d[k_from][v] + len < d[k_to][to]){
                            d[k_to][to] = d[k_from][v] + len;
                            q.push({-d[k_to][to], to});
                        }
                    }
                }
            }
        }

        cout << min(d[0][n-1], d[1][n-1]) << '\n';
    }

    return 0;
}