#include <bits/stdc++.h>
#define N 500011
#define ll long long
#define s1 first
#define s2 second
using namespace std;
int t,n,m;ll X;
struct edge{int u,v,w;};
vector<edge> ve;
int fa[N],siz[N];
int get(int a){return fa[a]==a?a:fa[a]=get(fa[a]);}
void merge(int a,int b)
{
	a=get(a);b=get(b);
	if(a==b)return;
	if(siz[a]<siz[b])swap(a,b);
	siz[a]+=siz[b];fa[b]=a;
}
bool cmp(edge a,edge b){return a.w<b.w;}
ll we[N];
vector<pair<int,ll> > G[N];
int dep[N],Fa[N][21],mx[N][21][2];
void dfs(int u,int F)
{
	dep[u]=dep[F]+1;Fa[u][0]=F;for(int i=1;i<=20;++i)Fa[u][i]=Fa[Fa[u][i-1]][i-1],mx[u][i][0]=max(mx[u][i-1][0],mx[Fa[u][i-1]][i-1][0]),mx[u][i][1]=max(mx[u][i-1][1],mx[Fa[u][i-1]][i-1][1]);
	for(int _=0;_<G[u].size();++_)if(G[u][_].s1^F)
	{
		int v=G[u][_].s1,w=G[u][_].s2;
		mx[v][0][w&1]=w;mx[v][0][(w&1)^1]=-1e9;
		dfs(v,u);
	}
}
int query(int u,int v,int o)
{
	if(dep[u]<dep[v])swap(u,v);int ans=0;
	for(int i=20;~i;--i)if(dep[u]-(1<<i)>=dep[v])ans=max(ans,mx[u][i][o]),u=Fa[u][i];if(u==v)return ans;
	for(int i=20;~i;--i)if(Fa[u][i]^Fa[v][i])ans=max({ans,mx[u][i][o],mx[v][i][o]}),u=Fa[u][i],v=Fa[v][i];return max({ans,mx[u][0][o],mx[v][0][o]});
	// int ans=0;
	// while(dep[u]>dep[v])ans=max(ans,mx[u][0]),u=Fa[u][0];
	// while(dep[u]<dep[v])ans=max(ans,mx[v][0]),v=Fa[v][0];
	// while(u^v)ans=max({ans,mx[u][0],mx[v][0]}),u=Fa[u][0],v=Fa[v][0];
	// return ans;
}
bool inT[N];
const int p=1e9+7;
int pw[N];
int main()
{
	pw[0]=1;for(int i=1;i<N;++i)pw[i]=(pw[i-1]+pw[i-1])%p;
	scanf("%d",&t);while(t--)
	{
		scanf("%d%d",&n,&m);
		ve.clear();
		for(int i=1;i<=n;++i)fa[i]=i,siz[i]=1;
		for(int i=1;i<=m;++i){int u,v,w;scanf("%d%d%d",&u,&v,&w);ve.push_back({u,v,w});}
		for(int i=1;i<=n;++i)G[i].clear();
		sort(ve.begin(),ve.end(),cmp);
		ll w=0;int cc=0;
		for(int i=0;i<m;++i)
		{
			if(get(ve[i].u)!=get(ve[i].v))
			{
				++cc;
				// printf("choose edge (%d)-(%d) w:%d\n",ve[i].u,ve[i].v,ve[i].w);
				G[ve[i].u].push_back({ve[i].v,ve[i].w});
				G[ve[i].v].push_back({ve[i].u,ve[i].w});
				merge(ve[i].u,ve[i].v);
				inT[i]=1;w+=ve[i].w;
			}
			else inT[i]=0;
		}
		if(cc<n-1)
		{
			printf("-1 -1\n");continue;
		}
		dfs(1,0);
		ll w_=1e18;
		for(int i=0;i<m;++i)
		{
			if(!inT[i])
			{
				int tt=query(ve[i].u,ve[i].v,(ve[i].w&1)^1);
				if(tt>=0)w_=min(w_,w+ve[i].w-tt);
			}
		}
		if(w%2==1)swap(w,w_);
		if(w<1e17)printf("%lld ",w);else printf("-1 ");
		if(w_<1e17)printf("%lld\n",w_);else printf("-1\n");
	}
	fclose(stdin);fclose(stdout);return 0;
}