#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 2e5 + 5, M = 5e5 + 5, LOG = 20, INF = (1 << 30);

struct DSU {
	int n, fa[N], siz[N];
	void init(int _n) { n = _n; for (int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1; }
	int father(int u) { return fa[u] = (fa[u] == u ? u : father(fa[u])); }
	void merge(int u, int v) {
		u = father(u), v = father(v);
		if (u == v) return;
		if (siz[u] < siz[v]) std::swap(u, v);
		fa[v] = u; siz[u] += siz[v];
	} 
	bool isSame(int u, int v) { return father(u) == father(v); }
} dsu;

int T, n, m;
int dep[N], st[2][LOG][N], fa[LOG][N];
bool mark[M];
std::array<int, 3> E[M];
std::vector<std::array<int, 2>> G[N];

void dfs(int u, int f) {
	dep[u] = dep[f] + 1;
	for (int i = 1; i < LOG; i++) {
		fa[i][u] = fa[i - 1][fa[i - 1][u]];
		st[0][i][u] = std::max(st[0][i - 1][u], st[0][i - 1][fa[i - 1][u]]);
		st[1][i][u] = std::max(st[1][i - 1][u], st[1][i - 1][fa[i - 1][u]]);
	}
	for (auto e : G[u]) {
		int v = e[0], w = e[1]; if (v == f) continue;
		st[w & 1][0][v] = w; fa[0][v] = u; dfs(v, u);
	}
}

int jump(int u, int v, int o) {
	if (dep[u] < dep[v]) std::swap(u, v);
	int ret = 0;
	for (int i = LOG - 1; ~i; i--) {
		if (dep[fa[i][u]] > dep[v]) {
			ret = std::max(ret, st[o ^ 1][i][u]);
			u = fa[i][u];
		}
	}
	u = fa[0][u]; if (u == v) return ret;
	for (int i = LOG - 1; ~i; i--) {
		if (fa[i][u] != fa[i][v]) {
			ret = std::max(ret, st[o ^ 1][i][u]);
			ret = std::max(ret, st[o ^ 1][i][v]);
			u = fa[i][u], v = fa[i][v];
		}
	}
	return ret;
}

void solve() {
	std::cin >> n >> m; dsu.init(n);
	for (int i = 1; i <= n; i++) {
		G[i].clear();
		for (int j = 0; j < LOG; j++) st[0][j][i] = st[1][j][i] = 0;
	}
	for (int i = 1; i <= m; i++) {
		int u, v, w; std::cin >> u >> v >> w;
		E[i] = {w, u, v}; mark[i] = 0;
	}
	std::sort(E + 1, E + 1 + m);
	i64 res = 0, ans[2] = {-1, -1}; int cnt = 0; 
	for (int i = 1; i <= m; i++) {
		int u = E[i][1], v = E[i][2], w = E[i][0];
		if (!dsu.isSame(u, v)) {
			cnt++; res += w; dsu.merge(u, v);
			G[u].push_back({v, w}); 
			G[v].push_back({u, w});
			mark[i] = 1;
		}
	}
	if (cnt != n - 1) return std::cout << "-1" << " " << "-1" << "\n", void();
	ans[res & 1] = res; dfs(1, 0); i64 min = INF;
	for (int i = 1; i <= m; i++) if (!mark[i]) {
		int u = E[i][1], v = E[i][2], w = E[i][0], max = jump(u, v, w & 1);
		if (max != 0) min = std::min(min, res - max + w);
	}
	if (min != INF) ans[!(res & 1)] = min;
	std::cout << ans[0] << " " << ans[1] << "\n";
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	std::cin >> T;
	while (T--) solve();

	return 0;
}