#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=(k);++i)
#define drp(i,j,k) for(int i=j;i>=(k);--i)
#define isdigit(ch) (ch>=48&&ch<=57)
#define mp std::make_pair
#define mod 998244353
#define MAXN 1000005
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
inline int read(){
	int x=0;
	bool sgn=true;
	char ch=getchar();
	while(!isdigit(ch)) sgn^=ch=='-',ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return sgn?x:-x;
}
inline ll readll(){
	ll x=0;
	bool sgn=true;
	char ch=getchar();
	while(!isdigit(ch)) sgn^=ch=='-',ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return sgn?x:-x;
}
template <typename tp> inline tp min(tp x,tp y){return x<y?x:y;}
template <typename tp> inline tp max(tp x,tp y){return x>y?x:y;}
template <typename tp> inline bool chkmin(tp &x,tp y){return x>y&&(x=y,true);}
template <typename tp> inline bool chkmax(tp &x,tp y){return x<y&&(x=y,true);}
int n,m,cur,tot,rt[MAXN],dep[MAXN],anc[MAXN][21];
ll ans[2];
bool vis[MAXN];
std::vector<pii> edge[MAXN];
struct data{
    int u,v,w;
    inline bool operator < (const data &rhs)const{
        return w<rhs.w;
    }
}a[MAXN];
struct info{
	int val[2];
	inline info operator + (const info &rhs)const{
		return (info){max(val[0],rhs.val[0]),max(val[1],rhs.val[1])};
	}
}mx[MAXN][21];
inline int find(int x){
    if(rt[x]==x) return x;
    return rt[x]=find(rt[x]);
}
inline void dfs(int u,int fa){
	dep[u]=dep[fa]+1,anc[u][0]=fa;
	rep(i,1,20) anc[u][i]=anc[anc[u][i-1]][i-1];
	rep(i,1,20) mx[u][i]=mx[u][i-1]+mx[anc[u][i-1]][i-1];
	for(auto [v,w]:edge[u]){
		if(v==fa) continue;
		mx[v][0].val[w&1]=w,dfs(v,u);
	}
}
inline info query(int x,int y){
	info ret=(info){0,0};
	if(dep[x]<dep[y]) std::swap(x,y);
	drp(i,20,0) if(dep[anc[x][i]]>=dep[y]) ret=ret+mx[x][i],x=anc[x][i];
	if(x==y) return ret;
	drp(i,20,0) if(anc[x][i]!=anc[y][i]){
		ret=ret+mx[x][i],x=anc[x][i];
		ret=ret+mx[y][i],y=anc[y][i];
	}
	return ret+mx[x][0]+mx[y][0];
}
inline void init(){
	cur=tot=0,ans[0]=ans[1]=0;
	rep(i,1,n) rt[i]=dep[i]=0,vis[i]=false,a[i]=(data){0,0,0};
	rep(i,1,n) rep(j,0,20) anc[i][j]=0,mx[i][j]=(info){0,0};
	rep(i,1,n) std::vector<pii>().swap(edge[i]);
}
int main(){
    drp(task,read(),1){
        n=read(),m=read(),init();
        rep(i,1,m) a[i].u=read(),a[i].v=read(),a[i].w=read();
        std::sort(a+1,a+m+1);
		rep(i,1,n) rt[i]=i;
		rep(i,1,m){
			int u=a[i].u,v=a[i].v,w=a[i].w;
			if(find(u)==find(v)) continue;
			++tot,vis[i]=true,ans[0]+=w,rt[find(u)]=find(v);
			edge[u].emplace_back(v,w);
			edge[v].emplace_back(u,w);
		}
		if(tot!=n-1){
			puts("-1 -1");
			continue;
		}
		if(!(ans[0]&1)) cur=0,ans[1]=1e18;
		else cur=1,std::swap(ans[0],ans[1]),ans[0]=1e18;
		dfs(1,0);
		rep(i,1,m) if(!vis[i]){
			int id=a[i].w&1;
			info tmp=query(a[i].u,a[i].v);
			if(tmp.val[id^1]) chkmin(ans[cur^1],ans[cur]+a[i].w-tmp.val[id^1]);
		}
		rep(i,0,1) if(ans[i]==1e18) ans[i]=-1;
		printf("%lld %lld\n",ans[0],ans[1]);
    }
}