#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<map>
#define LL long long
using namespace std;
const int mod=998244353;
const int Base=23,Base2=27;
inline int lowbit(int x){return x&(-x);}
inline int Jia(int x){return x>=mod?x-mod:x;}
inline int Jian(int x){return x>=0?x:x+mod;}
int KSM(int a,int b){
	int Ans=1;
	while(b){
		if(b&1)Ans=1LL*Ans*a%mod;
		a=1LL*a*a%mod;
		b>>=1;
	}
	return Ans;
}
inline int read(){
	int k=0,ty=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')ty=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		k=k*10+ch-'0';
		ch=getchar();
	}
	return k*ty;
}
int gcd(int a,int b){
	if(!b)return a;
	return gcd(b,a%b);
}
const int maxn=5e5+5;
struct dd{
	int x,y,z;
	bool operator<(const dd& A)const{
		return z<A.z;
	}
}b[maxn];
int h[maxn],cnt,n,m,fa[maxn],dept[maxn],top[maxn],DFN;
int Size[maxn],Son[maxn],vis[maxn],id[maxn];
LL Cost,Min[maxn*4][2],ans,ans1,ans2,vv[maxn];
int Get(int x){
	if(x==fa[x])return x;
	fa[x]=Get(fa[x]);
	return fa[x];
}
struct d{
	int to,next,val;
}E[maxn*2];
void add(int x,int y,int z){
	E[++cnt]=(d){y,h[x],z};
	h[x]=cnt;
	E[++cnt]=(d){x,h[y],z};
	h[y]=cnt;
}
bool Kruskal(){
	sort(b+1,b+1+m);Cost=0;
	for(int i=1;i<=n;++i)fa[i]=i;
	int all=0;
	for(int i=1;i<=m;++i)vis[i]=0;
	for(int i=1;i<=m;++i){
		int fx=Get(b[i].x),fy=Get(b[i].y);
		if(fx==fy)continue;
		vis[i]=1;
		add(b[i].x,b[i].y,b[i].z);
		fa[fx]=fy;Cost+=b[i].z;
		++all;
		if(all==n-1)return true;
	}
	return false;
}
void build(int now,int l,int r){
	Min[now][0]=Min[now][1]=1e18;
	if(l==r)return;
	int mid=l+r>>1;
	build(now*2,l,mid);
	build(now*2+1,mid+1,r);
}
void Change(int now,int l,int r,int p,int ty,LL v){
	if(l==r){
		Min[now][ty]=min(Min[now][ty],v);
		return;
	}
	int mid=l+r>>1;
	if(p<=mid)Change(now*2,l,mid,p,ty,v);
	else Change(now*2+1,mid+1,r,p,ty,v);
	Min[now][ty]=min(Min[now*2][ty],Min[now*2+1][ty]);
}
void Ask(int now,int l,int r,int ll,int rr,int ty){
	if(ll>r||rr<l)return;
	if(ll<=l&&rr>=r){
		ans=min(ans,Min[now][ty]);
		return;
	}
	int mid=l+r>>1;
	Ask(now*2,l,mid,ll,rr,ty);
	Ask(now*2+1,mid+1,r,ll,rr,ty);
}
void Ask(int x,int y,int ty){
	while(top[x]!=top[y]){
		if(dept[top[x]]<dept[top[y]])swap(x,y);
		Ask(1,1,n,id[top[x]],id[x],ty);
		x=fa[top[x]];
	}
	if(dept[x]<dept[y])swap(x,y);
	Ask(1,1,n,id[y],id[x],ty);
}
void dfs1(int x,int father,int deep,LL val){
	Size[x]=1;fa[x]=father;dept[x]=deep;
	Son[x]=0;vv[x]=val;
//	cout<<x<<'\n';
	for(int i=h[x];i;i=E[i].next){
		int y=E[i].to;
		if(y==fa[x])continue;
		dfs1(y,x,deep+1,E[i].val);
		Size[x]+=Size[y];
		if(Size[y]>Size[Son[x]])Son[x]=y;
	}
}
void dfs2(int x,int Top){
	id[x]=++DFN;top[x]=Top;
	Change(1,1,n,id[x],vv[x]&1,vv[x]);
	if(!Son[x])return;
	dfs2(Son[x],Top);
	for(int i=h[x];i;i=E[i].next){
		int y=E[i].to;
//		cout<<5<<'\n';
		if(y==Son[x]||y==fa[x])continue;
		dfs2(y,y);
	}
}
void Solve(){
	n=read();m=read();
	for(int i=1;i<=n;++i)h[i]=0;cnt=0;
	for(int i=1;i<=m;++i){
		b[i].x=read();b[i].y=read();b[i].z=read();
	}
	if(!Kruskal()){
		cout<<-1<<' '<<-1<<'\n';
		return;	
	}
//	for(int i=1;i<=m;++i)cout<<vis[i]<<'\n';
	build(1,1,n);
	dfs1(1,0,1,1e18);
//	cout<<"FAFAF\n";
	DFN=0;dfs2(1,1);
//	return;
//	cout<<Cost<<'\n';
	if(Cost&1)ans1=Cost,ans2=1e18;
	else ans2=Cost,ans1=1e18;
//	cout<<Cost<<' '<<ans1<<' '<<ans2<<'\n';
	LL CC=Cost;
	for(int i=1;i<=m;++i){
		if(vis[i])continue;
		int kk=(b[i].z&1);
		ans=1e18;
//		cout<<b[i].x<<' '<<b[i].y<<'\n';
		Ask(b[i].x,b[i].y,kk^1);
//		cout<<ans<<'\n';
		if(ans==1e18)continue;
		if(Cost&1)ans2=min(ans2,Cost-ans+b[i].z);
		else ans1=min(ans1,Cost-ans+b[i].z);
	}
//	cout<<"fff2\n";
	cout<<(ans2==1e18?-1:ans2)<<' '<<(ans1==1e18?-1:ans1)<<'\n';
}
int main(){
//	freopen("data.txt","r",stdin);
	int T=read();
	while(T--)Solve();
	return 0;
}