#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii = pair<int,int>;
const int N = 2e5 + 10, M = 5e5 + 10, D = 18, inf = 1e18;
struct node{int u,v,w;}ed[M];
int f[N], dep[N], fa[N][D+5], is[M];
pii ju[N][D+5];
int find(int x){return x == f[x] ? x : f[x] = find(f[x]);}
vector<pii>g[N];

void dfs(int x, int f)
{
	int i;
	fa[x][0] = f, dep[x] = dep[f] + 1;
	for(i=1;i<=D;i++)
		fa[x][i] = fa[fa[x][i-1]][i-1], ju[x][i] = max(ju[x][i-1],ju[fa[x][i-1]][i-1]);
	for(auto i:g[x])
	{
		int j = i.first, k = i.second;
		if(j==f) continue;
		if(k&1) ju[j][0] = make_pair(inf,k);
		else ju[j][0] = make_pair(k,inf);
		dfs(j,x);
	}
}

pii jump(int a, int b)
{
	pii ans = make_pair(-inf,-inf);
	int i;
	for(i=D;i>=0;i--) if(dep[fa[a][i]]>=dep[b]) ans = max(ans,ju[a][i]), a = fa[a][i];
	for(i=D;i>=0;i--) if(dep[fa[b][i]]>=dep[a]) ans = max(ans,ju[b][i]), b = fa[b][i];
	for(i=D;i>=0;i--) if(fa[a][i]!=fa[b][i])
		ans = max(ans,max(ju[a][i],ju[b][i])), a = fa[a][i], b = fa[b][i];
	if(a!=b) ans = max(ans,max(ju[a][0],ju[b][0]));
	return ans;
}

int Main()
{
	int n, m, i, cnt = 0, ans = 0, ans2 = inf;
	scanf("%lld%lld", &n, &m);
	for(i=1;i<=m;i++) scanf("%lld%lld%lld", &ed[i].u, &ed[i].v, &ed[i].w), is[i] = 0;
	sort(&ed[1],&ed[m]+1,[](node a,node b){return a.w<b.w;});
	for(i=1;i<=n;i++) f[i] = i;
	for(i=1;i<=m;i++)
	{
		int a = find(ed[i].u), b = find(ed[i].v);
		if(a!=b)
		{
			g[ed[i].u].emplace_back(ed[i].v,ed[i].w), g[ed[i].v].emplace_back(ed[i].u,ed[i].w);
			ans += ed[i].w, cnt++;
			is[i] = 1, f[a] = b;
		}
	}
	if(cnt<n-1)
	{
		for(i=1;i<=n;i++) g[i].clear();
		printf("-1 -1\n");
		return 0;
	}
	dfs(1,0);
	for(i=1;i<=m;i++) if(!is[i])
	{
		pair<int,int> x = jump(ed[i].u,ed[i].v);
		if(ed[i].w&1) ans2 = min(ans2,ans-x.first+ed[i].w);
		else ans2 = min(ans2,ans-x.second+ed[i].w);
	}
	if(ans2>=inf/10) ans2 = -1;
	if(ans&1) printf("%lld %lld\n", ans2, ans);
	else printf("%lld %lld\n", ans, ans2);
	for(i=1;i<=n;i++) g[i].clear();
	return 0;
}
signed main(){int t;scanf("%lld",&t);while(t--)Main();return 0;}