#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
#define FT first
#define SD second
const int N=500009;
int n,m,t,cnt;
pair<int,PII> e[N];
vector<PII> a[N];
vector<int> b;
int fa[N],f[22][N],dep[N];
LL mx_od[22][N],mx_ev[22][N];
LL ans,uans;
int find(int x)
{
	if(fa[x]!=x) fa[x]=find(fa[x]);
	return fa[x];
}
void merge(int x,int y)
{
	fa[find(x)]=y;
}
void dfs(int x,int fa)
{
	f[0][x]=fa;
	dep[x]=dep[fa]+1;
	for(PII i:a[x])
	{
		if(i.FT==fa) continue;
		if(i.SD%2) mx_od[0][i.FT]=i.SD,mx_ev[0][i.FT]=0xcfcfcfcfcfcfcfcf;
		else mx_ev[0][i.FT]=i.SD,mx_od[0][i.FT]=0xcfcfcfcfcfcfcfcf;
		dfs(i.FT,x);
	}
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		ans=cnt=0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d%d",&e[i].SD.FT,&e[i].SD.SD,&e[i].FT);
		}
		sort(e+1,e+m+1);
		for(int i=1;i<=n;i++) fa[i]=i;
		for(int i=1;i<=m;i++)
		{
			if(find(e[i].SD.FT)!=find(e[i].SD.SD))
			{
				merge(e[i].SD.FT,e[i].SD.SD),ans+=e[i].FT,cnt++;
				a[e[i].SD.FT].emplace_back(e[i].SD.SD,e[i].FT);
				a[e[i].SD.SD].emplace_back(e[i].SD.FT,e[i].FT);
			}
			else b.push_back(i);
		}
		if(cnt==n-1)
		{
			uans=0x3f3f3f3f3f3f3f3f+ans;
			mx_od[0][1]=mx_ev[0][1]=0xcfcfcfcfcfcfcfcf;
			dep[1]=0;
			dfs(1,1);
			for(int i=1;i<=20;i++)
				for(int j=1;j<=n;j++)
				{
					f[i][j]=f[i-1][f[i-1][j]];
					mx_od[i][j]=max(mx_od[i-1][j],mx_od[i-1][f[i-1][j]]);
					mx_ev[i][j]=max(mx_ev[i-1][j],mx_ev[i-1][f[i-1][j]]);
				}
			for(int i:b)
			{
				if(e[i].FT%2)
				{
					int x=e[i].SD.FT,y=e[i].SD.SD;
					LL oans=0xcfcfcfcfcfcfcfcf;
					if(dep[y]>dep[x]) swap(x,y);
					if(dep[x]!=dep[y])
					{
						for(int i=20;~i;i--)
						{
							if(dep[y]+(1<<i)>=dep[x]) oans=max(oans,mx_ev[i][x]),x=f[i][x];
						}
					}
					if(x!=y)
					{
						for(int i=20;~i;i--)
						{
							if(f[i][x]!=f[i][y])
								oans=max({oans,mx_ev[i][x],mx_ev[i][y]}),x=f[i][x],y=f[i][y];
						}
						oans=max({oans,mx_ev[0][x],mx_ev[0][y]});
					}
					uans=min(uans,ans-oans+e[i].FT);
				}
				else
				{
					int x=e[i].SD.FT,y=e[i].SD.SD;
					LL oans=0xcfcfcfcfcfcfcfcf;
					if(dep[y]>dep[x]) swap(x,y);
					if(dep[x]!=dep[y])
					{
						for(int i=20;~i;i--)
						{
							if(dep[y]+(1<<i)>=dep[x]) oans=max(oans,mx_od[i][x]),x=f[i][x];
						}
					}
					if(x!=y)
					{
						for(int i=20;~i;i--)
						{
							if(f[i][x]!=f[i][y])
								oans=max({oans,mx_od[i][x],mx_od[i][y]}),x=f[i][x],y=f[i][y];
						}
						oans=max({oans,mx_od[0][x],mx_od[0][y]});
					}
					uans=min(uans,ans-oans+e[i].FT);
				}
			}
			if(uans-ans>2e9) uans=-1;
			if(ans%2==0) printf("%lld %lld\n",ans,uans);
			else printf("%lld %lld\n",uans,ans);
		}
		else printf("-1 -1\n");
		for(int i=1;i<=n;i++) a[i].clear();
		b.clear();
	}
}
/*
3
2 1
1 2 5
3 1
1 3 1
4 4
1 2 1
1 3 1
1 4 1
2 4 2
  
3
6 6
1 3 3
1 4 6
2 5 2
1 3 4
6 5 4
2 1 1
  
 */