#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

const int MAXN = 1e5;
const int64_t inf = 1e18;

struct Edge
{
    int v;
    int w[2];

    Edge(){}
    Edge(int v, int a, int b)
    {
        this->v = v;
        this->w[0] = a;
        this->w[1] = b;
    }
};

int64_t dist[MAXN+5][2];

struct State
{
    int node;
    bool vehicle;

    State(){}
    State(int node, bool vehicle)
    {
        this->node = node;
        this->vehicle = vehicle;
    }

    int getDist() const
    {
        return dist[node][vehicle];
    }
};

bool operator <(State A, State B)
{
    if(A.getDist()!=B.getDist()) return A.getDist()<B.getDist();
    if(A.node!=B.node) return A.node<B.node;
    return A.vehicle<B.vehicle;
}

vector <Edge> graph[MAXN+5];

void useNode(State s, set <State> &states)
{
    if(s.vehicle==0 && dist[s.node][1]>dist[s.node][s.vehicle]+0)
    {
        dist[s.node][1] = dist[s.node][s.vehicle] + 0;
        states.insert(State(s.node, 1));
    }

    for(Edge e: graph[s.node])
    {
        if(dist[e.v][s.vehicle] > dist[s.node][s.vehicle] + e.w[s.vehicle])
        {
            dist[e.v][s.vehicle] = dist[s.node][s.vehicle] + e.w[s.vehicle];
            states.insert(State(e.v, s.vehicle));
        }
    }
}

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

void solveTestcase()
{
    int n, m;
    fin >> n >> m;

    for(int x = 1;x<=n;x++)
    {
        graph[x].clear();
        for(int v = 0;v<2;v++)
            dist[x][v] = inf;
    }

    for(int i = 0;i<m;i++)
    {
        int u, v, a, b;
        fin >> u >> v >> a >> b;

        graph[u].emplace_back(v, a, b);
        graph[v].emplace_back(u, a, b);
    }

    set <State> states;

    dist[1][0] = 0;
    states.insert(State(1, 0));

    while(states.empty()==false)
    {
        State s = *states.begin();
        states.erase(states.begin());

        useNode(s, states);
    }

    fout << min(dist[n][0], dist[n][1]) << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    fin.tie(nullptr);

    int T;
    fin >> T;

    while(T--) solveTestcase();
}