#include<iostream>
#include<cstdio>
#include<cmath>
#define lowbit(x) x&(-x)
#include<queue>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
int tt,n,m,u[500005],v[500005],f[500005],fa[22][200005],dep[500005];
ll w[500005],ma[2][22][200005];
struct Node{
	int u,v,tp;
	ll w;
}p[500005];
struct node{
	int to;
	ll w;
};
vector<node>e[200005];
bool cmp(Node a,Node b){
	return a.w<b.w;
}
int find(int x){
	if(x==f[x]) return x;
	return f[x]=find(f[x]);
}
void dfs(int u,int p){
	for(int i=0;i<e[u].size();++i){
		node x=e[u][i];
		int v=x.to;
		if(v==p) continue;
		fa[0][v]=u;
		ma[x.w%2][0][v]=max(x.w,ma[x.w%2][0][v]);
		if(!dep[v]){
			dep[v]=dep[u]+1;
			dfs(v,u);
		}
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=20;i>=0;--i) if(dep[fa[i][x]]>=dep[y]) x=fa[i][x];
	for(int i=20;i>=0;--i) if(fa[i][x]!=fa[i][y]) x=fa[i][x],y=fa[i][y];
	return fa[0][x];
}
ll cal(int x,int y,int tp){
	ll res=0;
	for(int i=20;i>=0;--i){
		if(dep[fa[i][x]]>=dep[y]){
			res=max(res,ma[tp^1][i][x]);
			x=fa[i][x];
		}
	}
	return res;
}
int main(){
	scanf("%d",&tt);
	while(tt--){
		ll sum=0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;++i){
			scanf("%d%d%lld",&p[i].u,&p[i].v,&p[i].w);
			p[i].tp=0;
		}
		for(int i=1;i<=n;++i) f[i]=i;
		sort(p+1,p+m+1,cmp);
		int cnt=0;
		for(int i=1;i<=m;++i){
			int a=find(p[i].u),b=find(p[i].v);
			if(a!=b){
				cnt++;
				sum+=p[i].w;
				e[p[i].u].push_back({p[i].v,p[i].w});
				e[p[i].v].push_back({p[i].u,p[i].w});
				f[a]=b;
				p[i].tp=1;
			}
		}
		dep[1]=1;
		dfs(1,0);
		for(int i=1;i<=20;++i)
			for(int j=1;j<=n;++j){
				fa[i][j]=fa[i-1][fa[i-1][j]];
				for(int k=0;k<=1;++k){
					ma[k][i][j]=max(ma[k][i-1][j],ma[k][i-1][fa[i-1][j]]);
				}
			}
		ll ans[2];
		ans[0]=ans[1]=1e18;
		ans[sum%2]=sum;
		for(int i=1;i<=m;++i){
			if(p[i].tp) continue;
			int g=lca(p[i].u,p[i].v);
			ll v1=cal(p[i].u,g,p[i].w%2),v2=cal(p[i].v,g,p[i].w%2);
			if(v1||v2) ans[(sum%2)^1]=min(ans[(sum%2)^1],sum-max(v1,v2)+p[i].w);
		}
		if(cnt!=n-1) ans[0]=ans[1]=-1;
		if(ans[(sum%2)^1]==1e18) ans[(sum%2)^1]=-1;
		printf("%lld %lld\n",ans[0],ans[1]);
		for(int i=1;i<=n;++i){
			e[i].clear();
			dep[i]=0;
			ma[0][0][i]=ma[1][0][i]=0;
		}
	}
}