#include <bits/stdc++.h>
using namespace std;

typedef pair <int, int> pii;
typedef long long ll;

const int N = 5e5 + 5, INF = 2e9;

vector <pii> adj[N];
int f[N], u[N], v[N], w[N], id[N], used[N], fa[N / 2][20], mx[N / 2][20][2], dep[N], ww[N];
int T, n, m;

bool cmp(int i, int j) {
	return w[i] < w[j];
}

int find(int x) {
	return f[x] == x ? x : f[x] = find(f[x]);
}

void dfs1(int u) {
	mx[u][0][0] = mx[u][0][1] = 0;
	mx[u][0][ww[u] % 2] = ww[u];
	for (int i = 1; i <= 17; i++) {
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
		for (int j = 0; j <= 1; j++) {
			mx[u][i][j] = max(mx[u][i - 1][j], mx[fa[u][i - 1]][i - 1][j]);
		}
	}
	for (auto v : adj[u]) {
		if (v.first == fa[u][0]) continue;
		fa[v.first][0] = u; ww[v.first] = v.second; dep[v.first] = dep[u] + 1; dfs1(v.first);
	}
}

int jump(int u, int k) {
	for (int i = 0; k; i++) {
		if ((k >> i) & 1) {
			u = fa[u][k];
			k ^= (1 << i);
		}
	}
	return u;
}

int query(int u, int k, int o) {
	int ans = 0;
	for (int i = 0; k; i++) {
		if ((k >> i) & 1) {
			ans = max(ans, mx[u][k][o]);
			u = fa[u][k];
			k ^= (1 << i);
		}
	}
	return ans;
}

int lca(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	u = jump(u, dep[u] - dep[v]);
	for (int i = 17; i >= 0; i--) {
		if (fa[u][i] != fa[v][i]) {
			u = fa[u][i];
			v = fa[v][i];
		}
	}
	return fa[u][0];
}

int qry(int u, int v, int o) {
	int d = lca(u, v);
	return max(query(u, dep[u] - dep[d], o), query(v, dep[v] - dep[d], o));
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> T;
	while (T--) {
		cin >> n >> m;
		for (int i = 1; i <= n; i++) f[i] = i;
		for (int i = 1; i <= n; i++) adj[i].clear();
		for (int i = 1; i <= m; i++) {
			cin >> u[i] >> v[i] >> w[i];
			id[i] = i;
		}
		sort(id + 1, id + m + 1, cmp);
		ll sum = 0;
		int mcnt = 0;
		for (int i = 1; i <= m; i++) {
			int x = find(u[id[i]]), y = find(v[id[i]]);
			if (x == y) used[id[i]] = 0;
			else {
				++mcnt;
				adj[u[id[i]]].emplace_back(v[i], w[id[i]]);
				adj[v[id[i]]].emplace_back(u[i], w[id[i]]);
				f[x] = y;
				used[id[i]] = 1;
				sum += w[id[i]];
			}
		}
		if (mcnt != n - 1) {
			cout << -1 << ' ' << -1 << '\n';
			continue;
		}
		dfs1(1);
		int ans = INF;
		for (int i = 1; i <= m; i++) {
			if (!used[i]) {
				int res = query(u[i], v[i], (w[i] % 2) ^ 1);
				if (res) ans = min(ans, w[i] - res);
			}
		}
		ll ans0 = -1, ans1 = -1;
		if (sum % 2 == 0) {
			ans0 = sum;
			if (ans != INF) ans1 = sum + ans;
		} else {
			ans1 = sum;
			if (ans != INF) ans0 = sum + ans;
		}
		cout << ans0 << ' ' << ans1 << '\n';
		
	}
	return 0;
}