#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MaxN=200000+10;
int n,m,u,v,c,ans,mnde,bel[MaxN],sm,t;
int fa[MaxN][21],dep[MaxN],mx[MaxN][21][2];
vector<pair<int,int>>V[MaxN];
priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<tuple<int,int,int>>>Q,Q2;
//doublizing
int find(int x){
	return (bel[x]==x?x:bel[x]=find(bel[x]));
}
void dfs(int u,int faa){
	for(int i=1;fa[u][i-1]>0;i++){
		fa[u][i]=fa[fa[u][i-1]][i-1];
		mx[u][i][0]=max(mx[u][i-1][0],mx[fa[u][i-1]][i-1][0]);
		mx[u][i][1]=max(mx[u][i-1][1],mx[fa[u][i-1]][i-1][1]);
	}
	for(auto [v,c]:V[u]){
		if(v==faa)continue;
		fa[v][0]=u;
		mx[v][0][c%2]=c;
		dep[v]=dep[u]+1;
		dfs(v,u);
	}
}
int lca(int a,int b,bool c){
	if(dep[a]<dep[b])swap(a,b);
	int delp=dep[a]-dep[b],res=-1;
	for(int i=20;i>=0;i--){
		if(delp&(1<<i)){
			res=m,max(res,mx[a][i][c]);
			a=fa[a][i];
		}
	}
	if(a==b)return res;
	for(int i=20;i>=0;i--){
		if(fa[a][i]!=fa[b][i]){
			res=max(res,max(mx[a][i][c],mx[b][i][c]));
			a=fa[a][i];
			b=fa[b][i];
		}
	}
	res=max(res,max(mx[a][0][c],mx[b][0][c]));
	return res;
}
void solve(){
	for(int i=1;i<=n;i++)V[i].clear();
	memset(mx+1,-1,sizeof(mx[0])*n);
	memset(fa+1,0,sizeof(fa[0])*n);
    // memset(mx,-1,sizeof(mx));
	// memset(fa,-1,sizeof(fa));
	mnde=100000000,ans=sm=0;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>c;
		if(u==v)continue;
		Q.emplace(c,u,v);
	}
	for(int i=1;i<=n;i++)bel[i]=i;
	while(!Q.empty()){
		auto [c,u,v]=Q.top();Q.pop();
		int a=find(u),b=find(v);
		if(a==b){ 
			Q2.emplace(c,u,v);//unchosen edge
			continue;
		}
		bel[a]=b;
		ans+=c;sm++;
		V[u].emplace_back(v,c);//build tree
		V[v].emplace_back(u,c);
	}
	if(sm+1<n){
		cout<<"-1 -1"<<endl;
		return ;
	}
	dfs(1,0);//f**king 	init for LCA
	while(!Q2.empty()){
		auto [c,u,v]=Q2.top();Q2.pop();
		int del=lca(u,v,abs(c%2-1));
		if(del>0)mnde=min(mnde,c-del);
	}
	if(mnde<=0||mnde>=100000000){
        if(ans%2)cout<<"-1 "<<ans<<endl;
        else cout<<ans<<" -1"<<endl;
    }else{
        if(ans%2)cout<<mnde+ans<<" "<<ans<<endl;
        else cout<<ans<<" "<<mnde+ans<<endl;
    }
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--){
		solve();
	}
}