#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=2e5+5,maxm=5e5+5,inf=-1ll<<60;
ll n,m;
struct edge1{
	ll x,y,val;
	friend bool operator < (const edge1 &x,const edge1 &y){
		return x.val==y.val?x.x<y.x:x.val<y.val;
	}
}E[maxm];
ll b[maxn];
vector<pair<ll,ll> >e[maxn];
#define mp make_pair
#define fi first
#define se second
#define pb push_back
ll fnd(ll x){return b[x]==x?x:fnd(b[x]);}//路径压缩
void merge(ll x,ll y){
	x=fnd(x),y=fnd(y);
	b[x]=y;
}
ll fa[maxn][19],dep[maxn];
ll mn[2][maxn][19];
void dfs(ll x){
	for(ll i=1;i<=18;i++){
		fa[x][i]=fa[fa[x][i-1]][i-1];
		// if(!fa[x][i])break;
	}
	for(ll i=1;i<=18;i++){
		// if(!fa[x][i])break;
		mn[0][x][i]=max(mn[0][fa[x][i-1]][i-1],mn[0][x][i-1]);
		mn[1][x][i]=max(mn[1][fa[x][i-1]][i-1],mn[1][x][i-1]);
	}
	for(auto it:e[x]){
		ll v=it.fi,val=it.se;
		if(v==fa[x][0])continue;
		fa[v][0]=x;
		mn[val&1][v][0]=val;
		dep[v]=dep[x]+1;
		dfs(v);
	}
}
ll query(ll x,ll y,ll ty){
	if(dep[x]<dep[y])swap(x,y);
	ll res=inf;
	for(ll i=18;i>=0;i--){
		if(dep[fa[x][i]]>=dep[y]){
			res=max(res,mn[ty][x][i]);
			x=fa[x][i];
		}
	}
	if(x==y)return res;
	for(ll i=18;i>=0;i--){
		if(fa[x][i]!=fa[y][i]){
			res=max(res,max(mn[ty][x][i],mn[ty][y][i]));
			x=fa[x][i],y=fa[y][i];
		}
	}
	res=max(res,max(mn[ty][x][0],mn[ty][y][0]));
	return res;
}
bool vis[maxm];
void solve(){
	cin>>n>>m;
	for(ll i=1;i<=n;i++)b[i]=i,e[i].clear();
	for(ll i=0;i<=n;i++){//1->0
		for(ll j=0;j<=18;j++){
			mn[0][i][j]=mn[1][i][j]=inf;
		}
	}
	for(ll i=1;i<=m;i++){
		cin>>E[i].x>>E[i].y>>E[i].val;
		vis[i]=0;
	}
	sort(E+1,E+1+m);
	ll sum=0,ans=-inf;
	for(ll i=1;i<=m;i++){
		ll x=E[i].x,y=E[i].y,val=E[i].val;
		x=fnd(x),y=fnd(y);
		if(x!=y)merge(x,y),sum+=val,e[E[i].x].pb(mp(E[i].y,val)),e[E[i].y].pb(mp(E[i].x,val)),vis[i]=1;
	}
	for(ll i=1;i<=n;i++){
		if(fnd(i)!=fnd(1)){
			cout<<"-1 -1"<<endl;
			return ;
		}
	}
	dep[1]=1;
	dfs(1);
	for(ll i=1;i<=m;i++){
		if(vis[i])continue;
		ans=min(ans,sum+E[i].val-query(E[i].x,E[i].y,(E[i].val&1)^1));
	}
	if(sum%2==1)swap(sum,ans);
	if(sum==-inf)sum=-1;
	if(ans==-inf)ans=-1;
	cout<<sum<<" "<<ans<<endl;
}
ll T=1;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}