#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:Find(f[x]);
}

vector<pair<int,int> > to[N];

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

void merge(int x,int y,int X,int Y,int w){
	to[X].emplace_back(Y,w);
	to[Y].emplace_back(X,w);
	if(sz[x]<sz[y]) f[x]=y,sz[y]+=sz[x];
	else f[y]=x,sz[x]+=sz[y];
	cnt++;
	sum+=w;
}

int fa[N],id[N],siz[N],idx;

void dfs(int u,int f){
	fa[u]=f,id[u]=++idx,siz[u]=1;
	for(pair<int,int> pl:to[u]){
		int v=pl.first,w=pl.second;
		if(v==f) continue;
		val[v]=w;
		dfs(v,u);
		siz[u]+=siz[v];
	}
}

int ff[N];
int FFind(int x){
	return x==ff[x]?x:ff[x]=FFind(ff[x]);
}

int mn,wdf,sb,s1,s2;
bool flg=0;

void check(int x,int y){
	if(id[s1]>=id[x]&&id[s1]<=id[x]+siz[x]-1&&id[s2]>=id[x]&&id[s2]<=id[x]+siz[x]-1) return;
	if(!x) return;
	if((val[x]&1)^(sb&1)){
		mn=max(mn,val[x]),flg=1;
		if(ff[x]==FFind(x)) ff[x]=FFind(fa[x]);
	}
	check(fa[FFind(x)],y);
}

/*
1
5 10
1 5 9
3 2 2
1 3 7
4 5 5
3 2 7
1 1 5
3 2 4
5 2 8
3 1 5
1 2 3
*/

signed main(){	
	// freopen("j.in","r",stdin);
	// freopen("test.out","w",stdout);
	T=read();
	while(T--){
		n=read(),m=read(),cnt=sum=idt=idx=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].u,e[i].v,e[i].w);
			
		}
		dfs(1,0);
		// cout<<cnt<<"\n";
		if(cnt<n-1){
			printf("-1 -1\n");
			for(int i=1;i<=n;i++) t[i]=val[i]=0,to[i].clear();
			continue;
		}
		int ans1=sum,ans2=1e16;idt=0;
		for(int i=1;i<=n;i++) f[i]=i,sz[i]=1,to[i].clear(),ff[i]=i;
		for(int i=1;i<=m;i++){
			int x=Find(e[i].u),y=Find(e[i].v);
			if(x==y){
				mn=0;
				sb=e[i].w,flg=0;
				s1=e[i].u,s2=e[i].v;
				check(e[i].u,1);
				check(e[i].v,1);

				if(flg) ans2=min(ans2,ans1-mn+e[i].w);
				continue;
			}
			merge(x,y,e[i].u,e[i].v,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,to[i].clear();
	}
	return 0;
}
/*
1
3 4
2 1 5
2 1 0
3 1 2
2 3 9
*/