#include <bits/stdc++.h>

using namespace std;

#define MAX 110000

#define PA pair<long long, long long>

long long t, n, m, a, b, c, d, tmp, ds1[MAX], ds2[MAX];
	
bool used[MAX];
	
priority_queue<PA, vector<PA>, greater<PA> > q;

vector<pair<long long, long long> > gr1[MAX], gr2[MAX];

void solve()
{
	long long ans = LLONG_MAX / 10;
	scanf("%lld%lld", &n, &m);
	fill(ds1, ds1 + n + 2, LLONG_MAX / 10);
	fill(ds2, ds2 + n + 2, LLONG_MAX / 10);
	fill(used, used + n + 2, false);
	for(int i = 0; i <= n; i++)
	{
		while(gr1[i].empty() == false)gr1[i].pop_back();
		while(gr2[i].empty() == false)gr2[i].pop_back();
	}
	for(int i = 0; i < m; i++)
	{
		scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
		gr1[a].push_back({b, c});
		gr1[b].push_back({a, c});
		gr2[a].push_back({b, d});
		gr2[b].push_back({a, d});
	}
	q.push({0, 1});
	ds1[1] = 0;
	while(q.size() > 0)
	{
		tmp = q.top().second;
		q.pop();
		if(used[tmp] == 1)continue;
		used[tmp] = 1;
		for(int i = 0; i < gr1[tmp].size(); i++)
		{
			if(ds1[gr1[tmp][i].first] > ds1[tmp] + gr1[tmp][i].second)
			{
				ds1[gr1[tmp][i].first] = ds1[tmp] + gr1[tmp][i].second;
				q.push({ds1[gr1[tmp][i].first], gr1[tmp][i].first});
			}
		}
	}
	
	fill(used, used + n + 2, false);
	
	q.push({0, n});
	ds2[n] = 0;
	while(q.size() > 0)
	{
		tmp = q.top().second;
		q.pop();
		if(used[tmp] == 1)continue;
		used[tmp] = 1;
		for(int i = 0; i < gr2[tmp].size(); i++)
		{
			if(ds2[gr2[tmp][i].first] > ds2[tmp] + gr2[tmp][i].second)
			{
				ds2[gr2[tmp][i].first] = ds2[tmp] + gr2[tmp][i].second;
				q.push({ds2[gr2[tmp][i].first], gr2[tmp][i].first});
			}
		}
	}
	for(int i = 1; i <= n; i++)
	{
		ans = min(ans, ds1[i] + ds2[i]);
	}
	cout << ans << endl;
	return ;
}

int main()
{
	freopen("hurry.in", "r", stdin);
	freopen("hurry.out", "w", stdout);
	cin >> t;
	for(int i = 1; i <= t; i++)solve();
	
	return 0;
}


/*

1
6
1 2 1 2 3 3

1
10
1 1 2 2 3 3 4 4 5 5

*/