#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10,M=5e5+10;
int n,m,F[N],dep[N],f[N][21][2],fa[N][21],lg[N];ll ans[2];
vector<pair<int,int> > g[N];
struct Edge
{
	int u,v,w,op;
}e[M];
bool cmp(Edge x,Edge y)
{
	return x.w<y.w;
}

int find(int x)
{
	return F[x]=x==F[x]?x:find(F[x]);
}

int solve(int u,int v,int op)
{
	int maxx=-1e9;
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=0;i<=lg[dep[u]-dep[v]];i++)
		if((1<<i)&(dep[u]-dep[v]))
			maxx=max(maxx,f[u][i][op]),u=fa[u][i];
	if(u==v) return maxx;
	for(int i=lg[dep[u]];i>=0;i--)
		if(fa[u][i]^fa[v][i])
		{
			u=fa[u][i],maxx=max(maxx,f[u][i][op]);
			v=fa[v][i],maxx=max(maxx,f[v][i][op]);
		}
	maxx=max(maxx,max(f[u][0][op],f[v][0][op]));
	return maxx;
}
void dfs(int p,int fath,int las)
{
	dep[p]=dep[fath]+1;
	fa[p][0]=fath;
	f[p][0][las&1]=las;
	f[p][0][las&1^1]=-1e9;
	for(int i=1;i<=lg[dep[p]];i++)
	{
		fa[p][i]=fa[fa[p][i-1]][i-1];
		for(int j=0;j<2;j++)
			f[p][i][j]=max(f[p][i-1][j],f[fa[p][i-1]][i-1][j]);
	}
	for(int i=0;i<g[p].size();i++)
	{
		int to=g[p][i].first;
		if(to==fath) continue;
		dfs(to,p,g[p][i].second);
	}
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d %d",&n,&m);
		for(int i=1;i<=n;i++) F[i]=i,g[i].clear();
		for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
		for(int i=1;i<=m;i++)
			scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w),e[i].op=0;
		sort(e+1,e+m+1,cmp);
		int cnt=0;ll sum=0;
		for(int i=1;i<=m;i++)
			if(find(e[i].u)!=find(e[i].v))
			{
				cnt++;e[i].op=1;sum+=e[i].w;
				g[e[i].u].push_back(make_pair(e[i].v,e[i].w));
				g[e[i].v].push_back(make_pair(e[i].u,e[i].w));
				F[find(e[i].u)]=find(e[i].v);
			}
		if(cnt!=n-1)
		{
			printf("-1 -1\n");
			continue;
		}
		ans[sum&1]=sum;
		ans[sum&1^1]=-1;
		dfs(1,0,-1e9);
		for(int i=1;i<=m;i++)
			if(!e[i].op)
			{
				int num=solve(e[i].u,e[i].v,e[i].w&1^1);
				if(num<0) continue;
				if(ans[sum&1^1]==-1ll) ans[sum&1^1]=sum-num+e[i].w;
				else ans[sum&1^1]=min(ans[sum&1^1],sum-num+e[i].w);
			}
		printf("%lld %lld\n",ans[0],ans[1]);
	}
}