// Problem: J. Even or Odd Spanning Tree
// Platform: undefined - The 3rd Universal Cup. Stage 8: Cangqian
// URL: https://contest.ucup.ac/contest/1780/problem/8941
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Author:British Union
// Long live UOB and koala
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5e5+5,INF=1e18;
int T,n,m;
struct edge{
	int u,v,w;
}E[maxn];
bool operator <(edge A,edge B){return A.w<B.w;}
struct LCT{
	vector<pair<int,int>> e[maxn];
	int fa[maxn],sze[maxn],son[maxn],dep[maxn],seg[maxn],to[maxn],rev[maxn],W[maxn];
	int st[maxn][19];
	int Max(int l,int r){
		if(l>r)return 0;
		int L=__lg(r-l+1);
		return max(st[l][L],st[r-(1<<L)+1][L]);
	}
	void dfs1(int u,int f){
		fa[u]=f,dep[u]=dep[f]+1,sze[u]=1;
		for(auto [v,w]:e[u]){
			if(v==f)continue;
			dfs1(v,u);
			sze[u]+=sze[v];W[v]=w;
			if(sze[v]>sze[son[u]])son[u]=v;
		}
	}
	void dfs2(int u,int t){
		to[u]=t,seg[u]=++seg[0],rev[seg[0]]=u;
		if(son[u])dfs2(son[u],t);
		for(auto [v,w]:e[u])if(v!=son[u]&&v!=fa[u])dfs2(v,v);
	}
	void predo(){
		dfs1(1,0);dfs2(1,1);
		for(int i=1;i<=n;i++)st[seg[i]][0]=W[i];
		for(int j=1;j<=18;j++)for(int i=1;i<=n;i++)st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
	}
	int task(int x,int y){
		int res=0;
		while(to[x]!=to[y]){
			if(dep[to[x]]<dep[to[y]])swap(x,y);
			res=max(res,Max(seg[to[x]],seg[x]));
			x=fa[to[x]];
		}
		if(dep[x]>dep[y])swap(x,y);
		res=max(res,Max(seg[x]+1,seg[y]));
		return res;
	}
	void clear(){
		for(int i=1;i<=n;i++){
			son[i]=0;
			for(int j=0;j<19;j++)st[i][j]=0;
			e[i].clear();
		}
	}
}Even,Odd;
int fa[maxn],tp[maxn];
void clear(){
	for(int i=1;i<=m;i++)tp[i]=0;
	Even.clear(),Odd.clear();
}
int Find(int x){
	return x==fa[x]?x:fa[x]=Find(fa[x]);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=m;i++)cin>>E[i].u>>E[i].v>>E[i].w;
		sort(E+1,E+m+1);
		for(int i=1;i<=n;i++)fa[i]=i;
		int W=0,qsy=0,cnt=0;
		for(int i=1;i<=m;i++){
			if(Find(E[i].u)==Find(E[i].v))continue;
			fa[Find(E[i].u)]=Find(E[i].v);
			tp[i]=1;W+=E[i].w,qsy+=(E[i].w&1);++cnt;
			if(E[i].w&1)Even.e[E[i].u].push_back({E[i].v,E[i].w}),Even.e[E[i].v].push_back({E[i].u,E[i].w}),Odd.e[E[i].u].push_back({E[i].v,0}),Odd.e[E[i].v].push_back({E[i].u,0});
			else Odd.e[E[i].u].push_back({E[i].v,E[i].w}),Odd.e[E[i].v].push_back({E[i].u,E[i].w}),Even.e[E[i].u].push_back({E[i].v,0}),Even.e[E[i].v].push_back({E[i].u,0});
		}
		if(cnt<n-1){cout<<-1<<" "<<-1<<endl;clear();continue;}
		int W2=INF;
		Even.predo(),Odd.predo();
		for(int i=1;i<=m;i++){
			if(tp[i]==1)continue;
			if(E[i].w&1){
				int mx=Odd.task(E[i].u,E[i].v);
				if(mx==0)continue;
				W2=min(W2,W-mx+E[i].w);
			}else{
				int mx=Even.task(E[i].u,E[i].v);
				if(mx==0)continue;
				W2=min(W2,W-mx+E[i].w);
			}
		}
		if(W2==INF)W2=-1;
		if(W&1)cout<<W2<<" "<<W<<endl;
		else cout<<W<<" "<<W2<<endl;
		clear();
	}
	return 0;
}