#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], n, m;
ll d[N], dp[N];

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--)
	{
		scanf("%d%d", &n, &m);
		_for(i, 1, n) g[i].clear();
		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) dp[i] = deg[i] = 0;
		_for(u, 1, n)
			for(auto [v, w, p]: g[u])
				if(d[v] == d[u] + w)
					deg[v]++;
		queue<int> q;
		_for(i, 1, n)
			if(!deg[i])
				q.push(i);
		while(!q.empty())
		{
			int u = q.front(); q.pop();
			for(auto [v, w, p]: g[u])
				if(d[v] == d[u] + w)
				{
					dp[v] = max(dp[v], dp[u] + p);
					if(--deg[v]== 0) q.push(v);
				}
		}
		printf("%lld\n", dp[n]);
	}

	return 0; 
}