#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<ll,ll>
const int N=3e5+50;
const ll inf=1e17;
int h[N],e[N],ne[N],idx,vis[N],d[N],cnt;
ll w[N],val[N];
void add(int u,int v,ll c,ll d){
	e[idx]=v,ne[idx]=h[u],w[idx]=c,val[idx]=d,h[u]=idx++;
}

struct node{
	int u;
	ll e,p;
	bool operator<(const node& a)const {
		if(e!=a.e){
			return e>a.e;
		}
		//p大的在前面 
		return p<a.p;
	}
};

int n,m;
int id[N],be[N];
pii ans[N];
void dij()
{
	for(int j=1;j<=n;j++)
	{
		//这个是拓扑的序列
		int u=be[j];
		if(ans[u].first==inf)	continue;
		for(int i=h[u];~i;i=ne[i]){
			int v=e[i];
			if(ans[v].first>ans[u].first+w[i])
			{
				ans[v].first=ans[u].first+w[i];
				ans[v].second=ans[u].second+val[i];
				continue;
			}
			if(ans[v].first==(ans[u].first+w[i])){
				ans[v].second=max(ans[v].second,ans[u].second+val[i]);
				continue;
			}
		} 
	}
}

int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		memset(h,-1,sizeof h);
		memset(d,0,sizeof d);
		idx=0;
		scanf("%d%d",&n,&m);
		for(int i=2;i<=n;i++){
			ans[i].first=inf;
			ans[i].second=0;
		}		
		for(int i=1;i<=m;i++)
		{
			int u,v;
			ll e,p;//如果是没有的点的话提前进行结束 
			scanf("%d%d%lld%lld",&u,&v,&e,&p);
			d[v]++;
			add(u,v,e,p);
		}//先选择补丢弃环 
		cnt=0;
		queue<int>q;
		for(int i=1;i<=n;i++){
			if(!d[i])
			{
				q.push(i);
			}
		}
		while(!q.empty()){
			int u=q.front();
			q.pop();
			id[u]=++cnt;
			be[cnt]=u;
			for(int i=h[u];~i;i=ne[i]){
				int v=e[i];
				d[v]--;
				if(!d[v]){
					q.push(v);
				}
			} 
		}
		cout<<(cnt==n)<<endl;
		dij();
		printf("%lld %lld\n",ans[n].first,ans[n].second);
	}
	return 0;
}