#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;

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

int t[N],val[N],f[N],sz[N],cnt,sum,idt;
inline int Find(int x){
	return x==f[x]?x:f[x];
}

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

void merge(int x,int y,int w){
	if(sz[x]<sz[y]) t[x]=++idt,val[x]=w,f[x]=y,sz[y]+=sz[x];
	else t[y]=++idt,val[y]=w,f[y]=x,sz[x]+=sz[y];
	cnt++;
	sum+=w;
}

bool vis1[N];
void jump1(int x,int y){
	vis1[x]=1;
	if(x==y) return;
	jump1(f[x],y);
}

bool vis2[N];
void jump2(int x,int y){
	vis2[x]=1;
	if(x==y) return;
	jump2(f[x],y);
}

void rejump1(int x,int y){
	vis1[x]=0;
	if(x==y) return;
	rejump1(f[x],y);
}

void rejump2(int x,int y){
	vis2[x]=0;
	if(x==y) return;
	rejump2(f[x],y);
}


int mn,wdf;

void check(int x,int y){
	if(x==y) return;
	if(vis1[x]&&vis2[x]) return;
	// if(t[x]>mn) mn=t[x],wdf=val[x];
	mn=max(mn,val[x]);
	check(f[x],y);
}

signed main(){	
	//freopen("road.in","r",stdin);
	//freopen("road.out","w",stdout);
	T=read();
	while(T--){
		n=read(),m=read(),cnt=sum=idt=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,sz[i]=1;
		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++) t[i]=val[i]=0;
			continue;
		}
		int ans1=sum,ans2=1e16;
		for(int i=1;i<=n;i++) f[i]=i,sz[i]=1;
		for(int i=1;i<=m;i++){
			int x=Find(e[i].u),y=Find(e[i].v);
			if(x==y){
				mn=0;
				jump1(e[i].u,x);
				jump2(e[i].v,y);
				check(e[i].u,x);
				check(e[i].v,y);
				rejump1(e[i].u,x);
				rejump2(e[i].v,y);
				if((e[i].w&1)^(mn&1))
					ans2=min(ans2,ans1-mn+e[i].w);
				continue;
			}
			merge(x,y,e[i].w);		
		}
		if(ans2==1e16) ans2=-1;
		if(ans1&1) swap(ans1,ans2);
		printf("%lld %lld\n",ans1,ans2);
		for(int i=1;i<=n;i++) t[i]=val[i]=0;
	}
	return 0;
}