#include<bits/stdc++.h>
namespace rgs = std::ranges;
using std::cin, std::cout;
using ll = long long;
using u64 = unsigned long long;
using db = double;
int T;


const int N = 200005;
struct edge {
	int u, v, w;
};
int n, m;
int anc[N];
int find(int x) {
	return anc[x] == x ? x : anc[x] = find(anc[x]);
}
std::vector<std::pair<int, int>> e[N];

int max[N][20][2];
int jump[N][20];
int dep[N];


const int inf = 1e9 + 10;
void dfs0(int x, int fa = 0) {
	dep[x] = dep[fa] + 1;
	for(int i = 1;i < 20;++i) {
		max[x][i][0] = std::max(max[x][i][0], max[jump[x][i - 1]][i][0]);
		max[x][i][1] = std::max(max[x][i][1], max[jump[x][i - 1]][i][1]);
		jump[x][i] = jump[jump[x][i - 1]][i - 1];
	}
	for(auto [i, w] : e[x]) if(i != fa) {
		max[i][0][0] = -inf;
		max[i][0][1] = -inf;
		max[i][0][w & 1] = w;
		jump[i][0] = x;
		dfs0(i, x);
	}
}
void up(int & x, int y) {
	if(x < y) x = y;
}
std::array<int, 2> query(int u, int v) {
	std::array<int, 2> ans{-inf, -inf};
	if(dep[u] > dep[v]) std::swap(u, v);
	for(int t = dep[v] - dep[u];t;t &= t - 1) {
		up(ans[0], max[v][__builtin_ctz(t)][0]);
		up(ans[1], max[v][__builtin_ctz(t)][1]);
		v = jump[v][__builtin_ctz(t)];
	}
	for(int i = 19;i >= 0;--i) {
		if(jump[u][i] != jump[v][i]) {
			up(ans[0], max[u][i][0]);
			up(ans[0], max[v][i][0]);
			up(ans[1], max[u][i][1]);
			up(ans[1], max[v][i][1]);
			u = jump[u][i];
			v = jump[v][i];
		}
	}
	if(u != v) {
		up(ans[0], max[u][0][0]);
		up(ans[0], max[v][0][0]);
		up(ans[1], max[u][0][1]);
		up(ans[1], max[v][0][1]);
	}
	return ans;
}

void solve() {
	cin >> n >> m;
	std::vector<edge> v;
	for(int i = 0, u, vv, w;i < m;++i) {
		cin >> u >> vv >> w;
		v.push_back({u, vv, w});
	}
	sort(v.begin(), v.end(), [](edge x, edge y) { return x.w < y.w; });
	for(int i = 1;i <= n;++i) {
		anc[i] = i;
	}
	int cc = 0;
	ll sum = 0;
	for(auto [u, v, w] : v) {
		if(find(u) != find(v)) {
			cc += 1;
			anc[find(u)] = find(v);
			e[u].emplace_back(v, w);
			e[v].emplace_back(u, w);
			sum += w;
		}
	}
	if(cc != n - 1) {
		cout << -1 << ' ' << -1 << '\n';
		return ;
	}
	dfs0(1);
	ll s2 = (ll) inf * inf;
	for(auto [u, v, w] : v) {
		auto res = query(u, v);
		if(res[w % 2 ^ 1] >= 0) {
			s2 = std::min(s2, sum + w - res[w % 2 ^ 1]);
		}
	}
	if(s2 == (ll) inf * inf) {
		s2 = -1;
	}
	if(sum % 2 == 1) {
		std::swap(sum, s2);
	}
	cout << sum << ' ' << s2 << '\n';
}
void clear() {
	memset(jump, 0, sizeof(jump[0]) * (n + 1));
	memset(max, 0, sizeof(max[0]) * (n + 1));
	memset(anc, 0, sizeof(anc[0]) * (n + 1));
	memset(dep, 0, sizeof(dep[0]) * (n + 1));
	memset(anc, 0, sizeof(anc[0]) * (n + 1));
	for(int i = 1;i <= n;++i) e[i].clear();
}
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
	cin >> T;
	for(int i = 0;i < T;++i) {
		solve();
		clear();
	}
}