#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 2e5 + 5;
const int maxm = 5e5 + 5;
const int maxlog = 17;
int n, m, flag, pa[maxn], val[maxn], f[2][maxn][maxlog + 1], fa[maxn][maxlog + 1], dep[maxn];
bool vis[maxn];
ll ans[2];
vector<pair<int, int>> g[maxn];
struct edge {
	int u, v, w;
} e[maxm];
int find(int x) {
	return (pa[x] == x) ? x : (pa[x] = find(pa[x]));
}
void dfs_pre(int u, int from) {
	dep[u] = dep[from] + 1;
	if(u != 1) {
		int o = val[u] & 1;
		f[o][u][0] = val[u];
		f[o ^ 1][u][0] = 0;
		fa[u][0] = from;
		for(int i = 1; i <= maxlog; i++) {
			f[0][u][i] = max(f[0][u][i - 1], f[0][fa[u][i - 1]][i - 1]);
			f[1][u][i] = max(f[1][u][i - 1], f[1][fa[u][i - 1]][i - 1]);
			fa[u][i] = fa[fa[u][i - 1]][i - 1];
		}
	}
	for(auto i : g[u]) {
		int v = i.first, w = i.second;
		if(v == from) {
			continue;
		}
		val[v] = w;
		dfs_pre(v, u);
	}
}
int LCA(int x, int y) {
	if(dep[y] > dep[x]) {
		swap(x, y);
	}
	for(int i = maxlog; i >= 0; i--) {
		if(dep[fa[x][i]] >= dep[y]) {
			x = fa[x][i];
		}
	}
	for(int i = maxlog; i >= 0; i--) {
		if(fa[x][i] != fa[y][i]) {
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0];
}
void work(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		cin >> e[i].u >> e[i].v >> e[i].w;
	}
	sort(e + 1, e + 1 + m, [&](const edge &x, const edge &y) {
		return x.w < y.w;
	});
	ans[0] = ans[1] = flag = -1;
	for(int i = 1; i <= n; i++) {
		pa[i] = i;
		vis[i] = 0;
		g[i].clear();
	}
	ll res = 0;
	int cnt = 0;
	for(int i = 1; i <= m; i++) {
		if(find(e[i].u) != find(e[i].v)) {
			res += e[i].w;
			pa[find(e[i].u)] = find(e[i].v);
			cnt++;
			vis[i] = 1;
		}
	}
	if(cnt < n - 1) {
		cout << -1 << ' ' << -1 << '\n';
		return;
	}
	flag = (res & 1) ^ 1;
	ans[flag ^ 1] = res;
	for(int i = 1; i <= m; i++) {
		if(vis[i]) {
			int u = e[i].u, v = e[i].v, w = e[i].w;
			g[u].emplace_back(v, w);
			g[v].emplace_back(u, w);
		}
	}
	dfs_pre(1, 0);
	for(int i = 1; i <= m; i++) {
		if(vis[i]) {
			continue;
		}
		int u = e[i].u, v = e[i].v, w = e[i].w;
		int lca = LCA(u, v), mx = 0, o = (w & 1) ^ 1;
//		cout << u << ' ' << v << ' ' << lca << ' ' << w << '\n';
		for(int i = maxlog; i >= 0; i--) {
			if(fa[u][i] && dep[fa[u][i]] >= dep[lca]) {
				mx = max(mx, f[o][u][i]);
				u = fa[u][i];
			}
			if(fa[v][i] && dep[fa[v][i]] >= dep[lca]) {
				mx = max(mx, f[o][v][i]);
				v = fa[v][i];
			}
		}
		if(mx > 0) {
			if(ans[flag] == -1) {
				ans[flag] = ans[flag ^ 1] - mx + w;
			}
			else {
				ans[flag] = min(ans[flag], ans[flag ^ 1] - mx + w);
			}
		}
	}
	cout << ans[0] << ' ' << ans[1] << '\n';
}


int main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin >> T;
	while(T--){
		work();
	}	
	return 0;
}