#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define lson 2*p
#define rson 2*p+1
#define x first
#define y second
const int N=3e5+10;
const int mod=1e9+7;
vector<int> g[N],scc[N];
vector<PII> h[N],G[N];
int n,m;
int tot,num,top,cnt;
int s[N],ins[N],c[N],a[N];
int dfn[N],low[N];
int u[N],v[N],e[N],p[N];
void tarjan(int x) {
	dfn[x]=low[x]=++num;
	s[++top]=x,ins[x]=1;
	for(int y:g[x]) {
		if(!dfn[y]) {
			tarjan(y);
			low[x]=min(low[x],low[y]);
		} else if(ins[y]) {
			low[x]=min(low[x],dfn[y]);
		}
	}
	if(dfn[x]==low[x]) {
		cnt++;
		int y;
		do {
			y=s[top--],ins[y]=0;
			c[y]=cnt,scc[cnt].push_back(y);
		} while(x!=y);
	}
}
void solve() {
    int n,m;
    cin>>n>>m;
    cnt=top=num=tot=0;
    for(int i=0; i<=n; i++) {
        h[i].clear();
        G[i].clear();
		g[i].clear();
		scc[i].clear();
		dfn[i]=low[i]=ins[i]=c[i]=s[i]=0;
	}
    for(int i=1;i<=m;i++) {
        cin>>u[i]>>v[i]>>e[i]>>p[i];
        h[u[i]].push_back({v[i],e[i]});
    }
    priority_queue<PII,vector<PII>,greater<PII> > q;
    vector<int> dist(n+10,1e18),vis(n+10,0);
    dist[1]=0;
    q.push({0,1});
    while(q.size()) {
        auto p1=q.top();
        q.pop();
        int x=p1.second;
        if(vis[x]) continue;
        vis[x]=1;
        for(auto it:h[x]) {
        	int y=it.x,z=it.y;
            if(dist[y]>dist[x]+z) {
                dist[y]=dist[x]+z;
                q.push({dist[y],y});
            }
        }
    }
	cout<<dist[n]<<" ";
	for(int x=1;x<=n;x++) {
		for(auto it:h[x]) {
			int y=it.x,z=it.y;
			if(dist[x]+z==dist[y]) g[x].push_back(y);
		}
	}
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
	queue<int> q1;
	vector<int> dp(n+10,0),deg(n+10,0);
    for(int i=1;i<=m;i++) {
        if(dist[u[i]]+e[i]==dist[v[i]]) {
        	if(c[u[i]]==c[v[i]]) continue;
            G[c[u[i]]].push_back({c[v[i]],p[i]});
            deg[c[v[i]]]++;
        }
    }
    q1.push(c[1]);
    while(q1.size()) {
        int x=q1.front();
        q1.pop();
        //cout<<x<<endl;
        for(auto it:G[x]) {
        	int y=it.x,z=it.y;
            dp[y]=max(dp[y],dp[x]+z);
            deg[y]--;
            if(!deg[y]) q1.push(y);
        }
    }
    cout<<dp[c[n]]<<endl;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T=1;
	cin>>T;
	while(T--) {
		solve();
	}
}