// Problem: Edges in MST
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF160D
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// Start coding at 2024-08-28 11:37:14
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
int n,m;
#define ll long long
const int M=2e5+5;
struct line{
	int u,v,w;
	int id;
}li[M];
bool vis[M];
#define int long long
inline bool operator <(const line &a,const line &b){return a.w<b.w;}
struct edge{int to,w,id;};
vector<edge> E[M];
int F[M];
int find(int x){return (x==F[x])?x:F[x]=find(F[x]);}
int dep[M],siz[M],fa[M],faE[M],hson[M],ltop[M],w[M],dfncnt,dfn[M],rk[M];
void dfs1(int now,int f){
	// cerr<<now<<" "<<f<<"\n";
	fa[now]=f;
	siz[now]=1;
	for(auto p:E[now]){
		if(p.to^f){
			w[p.to]=p.w;
			faE[p.to]=p.id;
			dep[p.to]=dep[now]+1;
			dfs1(p.to,now);
			siz[now]+=siz[p.to];
			if(siz[p.to]>siz[hson[now]])hson[now]=p.to;
		}
	}
	return;
}
void dfs2(int now,int top){
	ltop[now]=top;
	dfn[now]=++dfncnt;
	rk[dfncnt]=now;
	if(!hson[now])return;
	dfs2(hson[now],top);
	for(auto p:E[now])if(p.to^hson[now]&&p.to^fa[now])dfs2(p.to,p.to);
	return;
}
struct XDS{
	int omx[M<<2],emx[M<<2],tg[M<<2],mi[M<<2];
	inline void pushup(int now,bool typ=0){
		if(typ)omx[now]=max(omx[now<<1],omx[now<<1|1]),emx[now]=max(emx[now<<1],emx[now<<1|1]);
		mi[now]=min(mi[now<<1],mi[now<<1|1]);
		return;
	}
	inline void pushdown(int now){
		if(tg[now]!=INT_MAX){
			tg[now<<1]=min(tg[now<<1],tg[now]);
			tg[now<<1|1]=min(tg[now<<1|1],tg[now]);
			mi[now<<1]=min(mi[now<<1],tg[now]);
			mi[now<<1|1]=min(mi[now<<1|1],tg[now]);
			tg[now]=INT_MAX;
		}
		return;
	}
#define mid ((l+r)>>1)
	inline void build(int now,int l,int r){
		tg[now]=INT_MAX;
		if(l==r)return w[rk[l]]&1?(omx[now]=w[rk[l]],emx[now]=-2e9):(emx[now]=w[rk[l]],omx[now]=-2e9),void();
		build(now<<1,l,mid),build(now<<1|1,mid+1,r);
		return pushup(now,1);
	}
	inline int askomx(int now,int l,int r,int sl,int sr){
		if(sl==l&&r==sr)return omx[now];
		if(sl>mid)return askomx(now<<1|1,mid+1,r,sl,sr);
		if(sr<=mid)return askomx(now<<1,l,mid,sl,sr);
		return max(askomx(now<<1,l,mid,sl,mid),askomx(now<<1|1,mid+1,r,mid+1,sr));
	}
	inline int askemx(int now,int l,int r,int sl,int sr){
		if(sl==l&&r==sr)return emx[now];
		if(sl>mid)return askemx(now<<1|1,mid+1,r,sl,sr);
		if(sr<=mid)return askemx(now<<1,l,mid,sl,sr);
		return max(askemx(now<<1,l,mid,sl,mid),askemx(now<<1|1,mid+1,r,mid+1,sr));
	}
	inline int askmi(int now,int l,int r,int pos){
		if(l==r)return mi[now];
		pushdown(now);
		if(pos<=mid)return askmi(now<<1,l,mid,pos);
		return askmi(now<<1|1,mid+1,r,pos);
	}
	inline void mdf(int now,int l,int r,int sl,int sr,int val){
		if(sl<=l&&r<=sr)return mi[now]=min(mi[now],val),tg[now]=min(tg[now],val),void();
		pushdown(now);
		if(sl<=mid)mdf(now<<1,l,mid,sl,sr,val);
		if(sr>mid)mdf(now<<1|1,mid+1,r,sl,sr,val);
		return pushup(now);
	}
#undef mid
}T;
int taskomx(int u,int v){
	int res=0;
	while(ltop[u]!=ltop[v]){
		if(dep[ltop[u]]>dep[ltop[v]])res=max(T.askomx(1,1,n,dfn[ltop[u]],dfn[u]),res),u=fa[ltop[u]];
		else res=max(T.askomx(1,1,n,dfn[ltop[v]],dfn[v]),res),v=fa[ltop[v]];
	}
	if(u!=v)res=max(res,T.askomx(1,1,n,min(dfn[u],dfn[v])+1,max(dfn[u],dfn[v])));
	return res;
}
int taskemx(int u,int v){
	int res=0;
	while(ltop[u]!=ltop[v]){
		if(dep[ltop[u]]>dep[ltop[v]])res=max(T.askemx(1,1,n,dfn[ltop[u]],dfn[u]),res),u=fa[ltop[u]];
		else res=max(T.askemx(1,1,n,dfn[ltop[v]],dfn[v]),res),v=fa[ltop[v]];
	}
	if(u!=v)res=max(res,T.askemx(1,1,n,min(dfn[u],dfn[v])+1,max(dfn[u],dfn[v])));
	return res;
}
void tmdfmi(int u,int v,int val){
	while(ltop[u]!=ltop[v]){
		if(dep[ltop[u]]>dep[ltop[v]])T.mdf(1,1,n,dfn[ltop[u]],dfn[u],val),u=fa[ltop[u]];
		else T.mdf(1,1,n,dfn[ltop[v]],dfn[v],val),v=fa[ltop[v]];
	}
	if(u!=v)T.mdf(1,1,n,min(dfn[u],dfn[v])+1,max(dfn[u],dfn[v]),val);
	// cerr<<max(dfn[u],dfn[v])<<"\n";
	return;
}
int D;
ll ans1,ans2=1e9+5;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>D;
	while(D--){
		cin>>n>>m;
		ans1=0;ans2=1e9+5;
		dfncnt=0;
		for(int i=1;i<=n;i++)F[i]=i,E[i].clear(),hson[i]=0;
		for(int i=1;i<=n*4;i++)T.omx[i]=T.emx[i]=0;
		for(int i=1;i<=m;i++)cin>>li[i].u>>li[i].v>>li[i].w,li[i].id=i,vis[i]=0;
		sort(li+1,li+m+1);
		int fx,fy;
		int cnt=0;
		for(int i=1;i<=m;i++){
			fx=find(li[i].u),fy=find(li[i].v);
			if(fx==fy)continue;
			E[li[i].u].push_back((edge){li[i].v,li[i].w,li[i].id});
			E[li[i].v].push_back((edge){li[i].u,li[i].w,li[i].id});
			F[fx]=fy;
			vis[i]=1;
			cnt++;
			ans1+=li[i].w;
		}
		if(cnt!=n-1){cout<<"-1 -1\n";continue;}
		dfs1(1,0);
		// exit(0);
		dfs2(1,1);
		T.build(1,1,n);
		for(int i=1;i<=m;i++){
			if(vis[i])continue;
			if(li[i].w&1)ans2=min(li[i].w-taskemx(li[i].u,li[i].v),ans2);
			else ans2=min(li[i].w-taskomx(li[i].u,li[i].v),ans2);
		}
		if(ans2==1e9+5)ans2=-1;
		else ans2=ans1+ans2;
		if(ans1&1)cout<<ans2<<" "<<ans1<<"\n";
		else cout<<ans1<<" "<<ans2<<"\n";
	}
	return 0;
}