#include<bits/stdc++.h>
using namespace std;
using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
using u128=__uint128_t;
using pii=pair<int,int>;
#define fi first
#define se second
constexpr int N=2e5+5,M=5e5+5,INF=1e9;
constexpr ll LINF=1e18;
int n,m;
struct Edge{
	int u,v,w;
	Edge(){u=v=w=0;}
	Edge(int _u,int _v,int _w){u=_u,v=_v,w=_w;}
	inline bool operator <(const Edge &_)const{return w<_.w;}
};
Edge e[M];
struct edge{
	int y,z;
	edge(){y=z=0;}
	edge(int _y,int _z){y=_y,z=_z;}
};
vector<edge> Gr[N];
int fat[N],dep[N],siz[N],son[N],w[N];
int dfn[N],rnk[N],dfc,top[N];
void dfs1(int x,int fa){
	fat[x]=fa,dep[x]=dep[fa]+1;
	siz[x]=1,son[x]=0;
	for(auto &o:Gr[x])
		if(o.y!=fa){
			w[o.y]=o.z;
			dfs1(o.y,x);
			siz[x]+=siz[o.y];
			if(siz[son[x]]<siz[o.y])
				son[x]=o.y;
		}
}
void dfs2(int x,int tp){
	rnk[dfn[x]=++dfc]=x;
	top[x]=tp;
	if(!son[x])return;
	dfs2(son[x],tp);
	for(auto &o:Gr[x])
		if(o.y!=fat[x]&&o.y!=son[x])
			dfs2(o.y,o.y);
}
struct node{
	int a[2];
	node(){a[0]=a[1]=-INF;}
	node(int x){a[0]=a[1]=-INF,a[x&1]=x;}
	node(int _even,int _odd){a[0]=_even,a[1]=_odd;}
	inline node operator +(const node &_)const{
		return node(max(a[0],_.a[0]),max(a[1],_.a[1]));
	}
};
int lg[N];node st[19][N];
void initST(int n){
	lg[1]=0;for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
	for(int i=1;i<=n;i++)st[0][i]=w[rnk[i]];
	for(int i=1;i<=18;i++)
		for(int j=1;j+(1<<i)-1<=n;j++)
			st[i][j]=st[i-1][j]+st[i-1][j+(1<<(i-1))];
}
inline node query(int l,int r){
	int k=lg[r-l+1];
	return st[k][l]+st[k][r-(1<<k)+1];
}
inline node Query(int x,int y){
	node res;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		res=res+query(dfn[top[x]],dfn[x]);
		x=fat[top[x]];
	}
	if(dep[x]<dep[y])swap(x,y);
	if(x!=y)res=res+query(dfn[y]+1,dfn[x]);
	return res;
}
int f[N];
int get(int x){return f[x]==x?x:f[x]=get(f[x]);}
void merge(int x,int y){f[get(x)]=get(y);}
bool ck[M];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int _Test;cin>>_Test;
	while(_Test--){
		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++)f[i]=i,Gr[i].clear();
		int cnt=0;bool flag=0;
		ll sum=0,ans[2]={LINF,LINF};
		for(int i=1;i<=m;i++){
			ck[i]=0;
			int u=get(e[i].u),v=get(e[i].v),w=e[i].w;
			if(u==v)continue;
			Gr[u].emplace_back(v,w);
			Gr[v].emplace_back(u,w);
			merge(u,v);
			++cnt,ck[i]=1,sum+=w,flag^=w&1;
		}
		if(cnt<n-1){
			cout<<-1<<' '<<-1<<'\n';
			continue;
		}
		ans[flag]=sum;
		dfc=0,dfs1(1,0);
		dfs2(1,1);
		initST(n);
		for(int i=1;i<=m;i++){
			if(!ck[i]){
				int u=e[i].u,v=e[i].v,w=e[i].w;
				auto res=Query(u,v);
				if(res.a[!(w&1)]>0)
					ans[!flag]=min(ans[!flag],sum-res.a[!(w&1)]+w);
			}
		}
		if(ans[0]<LINF)cout<<ans[0]<<' ';
		else cout<<-1<<' ';
		if(ans[1]<LINF)cout<<ans[1]<<'\n';
		else cout<<-1<<'\n';
	}
	return 0;
}