#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lll __int128
#define pc __builtin_popcount
#define pr pair<int,int>
#define pb push_back
#define mp make_pair
#define x first
#define y second
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
ll rint(ll l,ll r){return uniform_int_distribution<ll>(l,r)(rnd);}
const int maxn=5e5+10;
int T,n,m,ans,cnt,bcj[maxn],dep[maxn],f[maxn][20],fe[maxn][20][2];
vector<pr> e[maxn];
bool use[maxn];
ll sum;
int root(int x){return (x==bcj[x])?x:(bcj[x]=root(bcj[x]));}
struct edge
{
	int x,y,z;
	edge(){}
	edge(int X,int Y,int Z){x=X,y=Y,z=Z;}
}a[maxn];
bool operator < (edge X,edge Y)
{
	return X.z<Y.z;
}
void dfs(int now,int fa)
{
	dep[now]=dep[fa]+1;
	for(int i=1;i<20;i++)
	{
		f[now][i]=f[f[now][i-1]][i-1];
		fe[now][i][0]=min(fe[now][i-1][0],fe[f[now][i-1]][i-1][0]);
		fe[now][i][1]=min(fe[now][i-1][1],fe[f[now][i-1]][i-1][1]);
	}
	for(pr i:e[now]) if(i.x!=fa) f[i.x][0]=now,fe[i.x][0][i.y&1]=i.y,dfs(i.x,now);
}
int calc(int x,int y,int typ)
{
	int res=2e9;
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=19;i>=0;i--)
		if(dep[f[x][i]]>=dep[y])
			res=min(res,fe[x][i][typ]),x=f[x][i];
	if(x==y) return res;
	for(int i=19;i>=0;i--)
		if(f[x][i]!=f[y][i])
			res=min({res,fe[x][i][typ],fe[y][i][typ]}),x=f[x][i],y=f[y][i];
	return min({res,fe[x][0][typ],fe[y][0][typ]});
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	scanf("%d",&T);
	for(int i=0;i<20;i++) fe[0][i][0]=fe[0][i][1]=2e9;
	while(T--)
	{
		scanf("%d%d",&n,&m),sum=0,cnt=0,ans=2e9;
		for(int i=1;i<=n;i++)
		{
			bcj[i]=i,e[i].clear();
			for(int j=0;j<20;j++) fe[0][j][0]=fe[0][j][1]=2e9;
		}
		for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z),use[i]=0;
		sort(a+1,a+m+1);
		for(int i=1;i<=m;i++)
		{
			if(root(a[i].x)!=root(a[i].y))
			{
				cnt++,use[i]=1,bcj[root(a[i].x)]=root(a[i].y),sum+=a[i].z;
				e[a[i].x].pb(mp(a[i].y,a[i].z)),e[a[i].y].pb(mp(a[i].x,a[i].z));
			}
		}
		if(cnt<n-1)
		{
			printf("-1 -1\n");
			continue;
		}
		dfs(1,0);
		for(int i=1;i<=m;i++)
		{
			if(!use[i])
			{
				int tmp=calc(a[i].x,a[i].y,(a[i].z&1)^1);
				if(tmp<=1e9) ans=min(ans,a[i].z-tmp);
			}
		}
		if(sum&1) printf("%lld %lld\n",(ans<=1e9)?sum+ans:-1,sum);
		else printf("%lld %lld\n",sum,(ans<=1e9)?sum+ans:-1);
	}
	return 0;
}