#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++) 
#define _for(i, a, b) for(int i = (a); i <= (b); i++) 
using namespace std;

typedef long long ll;
const int N = 1e5 + 10;
struct Edge 
{ 
	int v; ll w, p; 
	bool operator < (const Edge& rhs) const
	{
		return w > rhs.w;
	}
};
vector<Edge> g[N];
int deg[N], vis[N], n, m;
ll d[N], dp[N];
int dfn[N], low[N], st[N], co[N], top, cnt, id;
vector<pair<int, int>> G[N];

void dfs(int u)
{
	dfn[u] = low[u] = ++cnt;
	st[++top] = u;

	for(auto [v, w, p]: g[u])
		if(d[v] == d[u] + w)
		{
			if(!dfn[v])
			{
				dfs(v);
				low[u] = min(low[u], low[v]);
			}
			else if(!co[v]) low[u] = min(low[u], dfn[v]);
		}
	
	if(low[u] == dfn[u])
	{
		id++;
		while(1)
		{
			co[st[top--]] = id;
			if(st[top + 1] == u) break;
		}
	}
}

void solve()
{
	_for(i, 1, n) d[i] = 1e18;
	d[1] = 0;
	priority_queue<Edge> q;
	q.push({1, d[1], 0});

	while(!q.empty())
	{
		Edge x = q.top(); q.pop();
		int u = x.v;
		if(d[u] != x.w) continue;

		for(auto [v, w, p]: g[u])
			if(d[v] > d[u] + w)
			{
				d[v] = d[u] + w;
				q.push({v, d[v], 0});
			}
	}
}

int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		cnt = top = id = 0;
		scanf("%d%d", &n, &m);
		_for(i, 1, n) g[i].clear(), G[i].clear(), low[i] = dfn[i] = co[i] = dp[i] = deg[i] = 0;
		while(m--)
		{
			int u, v, w, p;
			scanf("%d%d%d%d", &u, &v, &w, &p);
			g[u].push_back({v, w, p});
		}

		solve();
		printf("%lld ", d[n]);

		_for(i, 1, n)
			if(!dfn[i])
				dfs(i);
		_for(u, 1, n)
			for(auto [v, w, p]: g[u])
				if(d[v] == d[u] + w)
					if(co[u] != co[v])
					{
						G[co[u]].push_back({co[v], p});
						deg[co[v]]++;
					}
		
		queue<int> q;
		_for(i, 1, id)
			if(!deg[i])
				q.push(i);
		while(!q.empty())
		{
			int u = q.front(); q.pop();
			for(auto [v, p]: G[u])
			{
				dp[v] = max(dp[v], dp[u] + p);
				if(--deg[v]== 0) q.push(v);
			}
		}
		printf("%lld\n", dp[co[n]]);
	}

	return 0; 
}