#include<bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
#define ll long long
using namespace std;
const int N=2e5+5,M=5e5+5,INF=0x3f3f3f3f;
const ll IINF=0x3f3f3f3f3f3f3f3f;
struct node{
	int u,v,w;
	bool operator < (const node &x) const{
		return w<x.w;
	}
}edg[M];
int T,n,m,a,b,c,dep[N],f[N],fa[N][20],mx[2][N][20];
ll tmp,ans[2];
vector<pii > e[N];
bool vis[N];
int getfa(int x) {return f[x]==x?x:(f[x]=getfa(f[x]));}
int merge(int x,int y,int w)
{
	int fx=getfa(x),fy=getfa(y);
	if(fx==fy) return 0;
	e[x].push_back({y,w});
	e[y].push_back({x,w});
	f[fy]=fx;
	tmp+=w;
	return 1;
}
void Dfs(int x,int pre,int w)
{
	dep[x]=dep[pre]+1;fa[x][0]=pre;mx[w&1][x][0]=w;
	for(int i=1;(1<<i)<dep[x];i++)
	{
		fa[x][i]=fa[fa[x][i-1]][i-1];
		mx[0][x][i]=max(mx[0][x][i-1],mx[0][fa[x][i-1]][i-1]);
		mx[1][x][i]=max(mx[1][x][i-1],mx[1][fa[x][i-1]][i-1]);
	}
	for(auto v:e[x])
	{
		if(v.first==pre) continue;
		Dfs(v.first,x,v.second);
	}
	return;
}
int LCA(int x,int y,int tp)
{
	if(dep[x]>dep[y]) swap(x,y);
	int res=0;
	for(int i=19;i>=0;i--) if(dep[fa[y][i]]>=dep[x]) res=max(res,mx[tp][y][i]),y=fa[y][i];
	for(int i=19;i>=0;i--) if(fa[x][i]!=fa[y][i]) res=max(res,max(mx[tp][x][i],mx[tp][y][i])),x=fa[x][i],y=fa[y][i];
	res=max(res,max(mx[tp][x][0],mx[tp][y][0]));
	return res;
}
void solve()
{
	int cnt=0,s;ans[0]=ans[1]=-1;
	sort(edg+1,edg+m+1);tmp=0;
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<=m;i++)
	{
		if(merge(edg[i].u,edg[i].v,edg[i].w)) cnt++,vis[i]=true;
		if(cnt==n-1) break;
	}
	if(cnt!=n-1) return;
	ans[tmp&1]=tmp;ans[(tmp&1)^1]=IINF;
	Dfs(1,0,0);
	for(int i=1;i<=m;i++)
	{
		if(!vis[i])
		{
			s=LCA(edg[i].u,edg[i].v,(edg[i].w&1)^1);
			if(s) ans[(tmp&1)^1]=min(ans[(tmp&1)^1],tmp+edg[i].w-s);
		}
	}
	if(ans[(tmp&1)^1]==IINF) ans[(tmp&1)^1]=-1;
	return;
}
int 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>>edg[i].u>>edg[i].v>>edg[i].w;
		solve();
		cout<<ans[0]<<" "<<ans[1]<<"\n";
		for(int i=1;i<=n;i++) e[i].clear();
		for(int i=1;i<=m;i++) vis[i]=false;
		for(int i=1;i<=n;i++) for(int j=0;j<20;j++) mx[0][i][j]=mx[1][i][j]=0;
	}
	return 0;
}