#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],fa[N],f[N][20],g[N][20],_fa[N][20],llg[N]; //f odd edge  g even edge
map<pair<int,int>,int>id;

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]);}

struct Edge{
	int x,y,z,id;
	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=head[x];i;i=suiv[i])
		{
			int y=ver[i],z=edge[i];
			if(y==fa)continue;
			if(z&1)f[y][0]=z;
			else g[y][0]=z;
			_fa[y][0]=x;
			dep[y]=dep[x]+1;
			dfs(y,x);
		}
	}

	inline void cal()
	{
		for(int i=1;i<=n;i++)
			for(int j=1;1<<j<=dep[i];j++)
				_fa[i][j]=_fa[_fa[i][j-1]][j-1];
		for(int i=1;i<=n;i++)
			for(int j=1;1<<j<=dep[i];j++)
				f[i][j]=max(f[i][j-1],f[_fa[i][j-1]][j-1]),
				g[i][j]=max(g[i][j-1],g[_fa[i][j-1]][j-1]);
	}

	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]});
			}
		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);
		for(int i=1;i<=m;i++)
			a[i].id=i;
		init(n);
		int cnt=0;
		for(int i=1;i<=m;i++)
		{
			int fx=find(a[i].x),fy=find(a[i].y);
			if(fx==fy)continue;
			fa[fx]=fy;
			istree[a[i].id]=1;
			evenans+=1ll*a[i].z;
			id[make_pair(a[i].x,a[i].y)]=id[make_pair(a[i].y,a[i].x)]=a[i].id;
			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]=1;
		e.dep[1]=1;
		e.dfs(1);
		e.cal();
		

		//cout<<evenans<<endl;
		ll add=inf;
		for(int i=1,treeedge;i<=m;i++)
		{
			int res=-inf;
			if(istree[a[i].id])continue;
			if((treeedge=id[make_pair(a[i].x,a[i].y)]))
			{
				if((a[treeedge].z%2)==(a[i].z%2))continue;
				add=min(add,1ll*abs(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;

}