#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;

const int N=500010;
const int inf=1000000000;
typedef long long ll;
int n,m,istree[N],f[N][20],g[N][20],_fa[N][20],llg[N]; //f odd edge  g even edge
//unordered_map<ll,int>id;

inline ll _(int x,int y){return 1ll*(1ll*x-1)*n+y;}
struct disunion{
	int fa[N];
	inline void init(int x){for(int i=1;i<=x;i++)fa[i]=i;}
	inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
}t;

struct Edge{
	int x,y,z;
	inline bool operator<(const Edge that){
		return z<that.z;
	}
}a[N];

struct Graph{
	int tot,head[N],suiv[N],edge[N],ver[N],dep[N];

	inline void init(int x)
	{
		for(int i=1;i<=x;i++)
			head[i]=0;
		tot=0;
	}

	inline void lnk(int x,int y,int z)
	{
		ver[++tot]=y;
		edge[tot]=z;
		suiv[tot]=head[x];
		head[x]=tot;
	}

	inline void dfs(int x,int fa=-1)
	{
		for(int i=1;(1<<i)<=dep[x];i++)
			_fa[x][i]=_fa[_fa[x][i-1]][i-1],
			f[x][i]=max(f[x][i-1],f[_fa[x][i-1]][i-1]),
			g[x][i]=max(g[x][i-1],g[_fa[x][i-1]][i-1]);
		for(int i=head[x];i;i=suiv[i])
		{
			int y=ver[i],z=edge[i];
			if(y==fa)continue;
			if(z&1)f[y][0]=z,g[y][0]=-inf;
			else g[y][0]=z,f[y][0]=-inf;
			_fa[y][0]=x;
			dep[y]=dep[x]+1;
			dfs(y,x);
		}
	}

	inline int query(int x,int y,int op)   //op==0 query odd(f) op==1 query even(g)
	{
		int res=-inf;
		if(dep[x]<dep[y])swap(x,y);
		while(dep[x]>dep[y])
		{
			if(!op)res=max(res,f[x][llg[dep[x]-dep[y]]]);
			else res=max(res,g[x][llg[dep[x]-dep[y]]]);
			x=_fa[x][llg[dep[x]-dep[y]]];
		}
		if(x==y)return res;
		for(int i=llg[dep[x]];i>=0;i--)
			if(_fa[x][i]!=_fa[y][i])
			{
				if(!op)res=max({res,f[x][i],f[y][i]});
				else res=max({res,g[x][i],g[y][i]});
				x=_fa[x][i];
				y=_fa[y][i];
			}
		if(!op)return max({res,f[x][0],f[y][0]});
		else return max({res,g[x][0],g[y][0]});
	}
}e;
			

signed main()
{
	for(int i=1;i<N;i++)
		llg[i]=log2(i);
	int T;
	scanf("%d",&T);
	while(T--)
	{
		//id.clear();	
		ll evenans=0,oddans=0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++)
			scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
		sort(a+1,a+1+m);
		t.init(n);
		int cnt=0;
		for(int i=1;i<=m;i++)
		{
			int fx=t.find(a[i].x),fy=t.find(a[i].y);
			if(fx==fy)continue;
			t.fa[fx]=fy;
			istree[i]=1;
			evenans+=1ll*a[i].z;
			//id[_(a[i].x,a[i].y)]=id[_(a[i].y,a[i].x)]=i;
			e.lnk(a[i].x,a[i].y,a[i].z);
			e.lnk(a[i].y,a[i].x,a[i].z);
			cnt++;
		}
		if(cnt<n-1)
		{
			puts("-1 -1");
			for(int i=1;i<=m;i++)
				istree[i]=0;
			e.init(n);
			continue;
		}
		for(int i=1;i<=n;i++)
			for(int j=0;j<20;j++)
				f[i][j]=g[i][j]=-inf;
		_fa[1][0]=0;
		e.dep[1]=1;
		e.dfs(1);
		
		//while(1)
		//{
		//	int x,y,z;
		//	cin>>x>>y>>z;
		//	cout<<e.query(x,y,z)<<endl;
		//}
		//cout<<evenans<<endl;
		ll add=inf;
		for(int i=1,treeedge;i<=m;i++)
		{
			int res=-inf;
			if(istree[i])continue;
			/*
			if((treeedge=id[_(a[i].x,a[i].y)]))
			{
				if((a[treeedge].z%2)==(a[i].z%2))continue;
				add=min(add,1ll*abs(1ll*a[treeedge].z-a[i].z));
				continue;
			}*/
			if(a[i].z&1)//odd
				res=e.query(a[i].x,a[i].y,1);
			else res=e.query(a[i].x,a[i].y,0);
			if(res!=-inf)
				add=min(add,abs(res-1ll*a[i].z));
		}
		//cout<<"!"<<endl;
		if(add!=inf)oddans=evenans+add;
		else oddans=-1;
		if(evenans&1)swap(evenans,oddans);
		printf("%lld %lld\n",evenans,oddans);
		for(int i=1;i<=m;i++)
			istree[i]=0;
		e.init(n);
	}
	return 0;
}