#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];

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] = vis[i] = 0;
		deque<int> q;
		q.push_front(1);
		vis[1] = 1;

		while(!q.empty())
		{
			int u = q.front(); q.pop_front();
			vis[u] = 0;
			for(auto [v, w, p]: g[u])
				if(d[v] == d[u] + w)
					if(dp[v] < dp[u] + p)
					{
						dp[v] = dp[u] + p;
						if(!vis[v]) 
						{
							if(!q.empty() && d[v] > d[q.front()]) q.push_front(v);
							else q.push_back(v);
							vis[v] = 1;
						}
					}
		}
		printf("%lld\n", dp[n]);
	}

	return 0; 
}