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

long long const INF = 1e18;

struct Tel{
	int st;
	int car, byke;
};
vector<Tel> v[100001];
long long rc[100001], rb[100001];
bool fl[100001];
int n;

void dijkstra(int k){
    fl[k]=1;
    int i;
    for(i=0;i<v[k].size();i++){
        if(rc[v[k][i].st] > rc[k] + v[k][i].car) rc[v[k][i].st] = rc[k] + v[k][i].car;
    }
    long long minn=INF;
    int ks=k;
    for(i=1;i<=n;i++){
        if(minn > rc[i] && fl[i] == 0)minn = rc[i], k=i;
    }
    if(k == ks)return;
    dijkstra(k);
}


void dijkstra2(int k){
    fl[k]=1;
    int i;
    for(i=0;i<v[k].size();i++){
        if(rb[v[k][i].st] > rb[k] + v[k][i].byke) rb[v[k][i].st] = rb[k] + v[k][i].byke;
    }
    long long minn=INF;
    int ks=k;
    for(i=1;i<=n;i++){
        if(minn > rb[i] && fl[i] == 0)minn = rb[i], k=i;
    }
    if(k == ks)return;
    dijkstra2(k);
}

int main()
{
	freopen("hurry.in", "r", stdin);
	freopen("hurry.out", "w", stdout);
	int t;
	cin>>t;
	while(t--) {
		int m;
		cin>>n>>m;
		int i;
		for(i=1;i<=m;i++) {
			int p, q, car, by;
			cin>>p>>q>>car>>by;
			v[p].push_back({q, car, by});
			v[q].push_back({p, car, by});
		}
		fill(rc, rc+n+1, INF);
		fill(rb, rb+n+1, INF);
		fill(fl, fl+n+1, 0);
		rc[1] = 0;
		dijkstra(1);
		rb[n] = 0;
		fill(fl, fl+n+1, 0);
		dijkstra2(n);
		long long minn = INF;
		for(i=1;i<=n;i++) {
			minn = min(minn, rc[i]+rb[i]);
			v[i].erase(v[i].begin(), v[i].end());
		}
		cout<<minn<<endl;
	}

	return 0;
}