#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-48,ch=getchar();}
	return x*f;
}
int T,n,m,ans;

struct Node{
	int u,v,w;
}e[N];

map<int,int> mp[N];
int f[N],cnt,sum;
vector<int> p[N];
inline int Find(int x){
	return x==f[x]?x:f[x]=Find(f[x]);
}

bool cmp(Node a,Node b){
	return a.w<b.w;
}

void merge(int x,int y,int w){
	if(p[x].size()<p[y].size()){
		f[x]=y;
		for(int u:p[x]) 
			p[y].emplace_back(u),mp[u][y]=w;
	}
	else{
		f[y]=x;
		for(int u:p[y]) 
			p[x].emplace_back(u),mp[u][x]=w;		
	}
	cnt++;
	sum+=w;
}

signed main(){	
	//freopen("road.in","r",stdin);
	//freopen("road.out","w",stdout);
	T=read();
	while(T--){
		n=read(),m=read(),ans=cnt=sum=0;
		for(int i=1;i<=m;i++){
			e[i].u=read();
			e[i].v=read();
			e[i].w=read();
		}
		sort(e+1,e+1+m,cmp);
		for(int i=1;i<=n;i++) f[i]=i,p[i].emplace_back(i);
		for(int i=1;i<=m;i++){
			int x=Find(e[i].u),y=Find(e[i].v);
			if(x==y) continue;
			merge(x,y,e[i].w);
		}
		if(cnt<n-1){
			printf("-1 -1\n");
			for(int i=1;i<=n;i++) p[i].clear(),mp[i].clear();
			continue;
		}
		int ans1=sum,ans2=-1;
		for(int i=1;i<=n;i++) f[i]=i;
		for(int i=1;i<=m;i++){
			int x=Find(e[i].u),y=Find(e[i].v);
			if(x==y){
				int o=max(mp[e[i].u][x],mp[e[i].v][x]);
				if((o&1)^(e[i].w&1)){
					ans2=ans1+e[i].w-o;
					break;
				}
				continue;
			}
			merge(x,y,e[i].w);			
		}
		if(ans1&1) swap(ans1,ans2);
		printf("%lld %lld\n",ans1,ans2);
		for(int i=1;i<=n;i++) p[i].clear(),mp[i].clear();
	}
	return 0;
}