#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) ::begin(x), ::end(x)
void _d(auto... x) { ((cerr << ' ' << x), ...) << endl; }
#define debug(x...) cerr << "["#x"]:", _d(x)

vector<vector<pair<int, ll>>> adj;
vector<int> d, par, jump;
using T = array<ll, 2>;
vector<T> pval, jval;

constexpr T E = T{(ll)-1e18, (ll)-1e18}; // neutral element for comb
T comb(T a, T b) {return {max(a[0], b[0]), max(a[1], b[1])};} // commutative + associative

void addNode(int v, int from, ll w) {
	d[v] = d[from] + 1;
	par[v] = jump[v] = from;
    T idk = E;
    idk[w%2] = w;
	pval[v] = jval[v] = idk;
	if (int p = jump[from]; d[jump[p]] - d[p] == d[p] - d[from]) {
		jump[v] = jump[p];
		jval[v] = comb(comb(idk, jval[from]), jval[p]);
}}

void dfs(int v, int from) {
	for (auto [u, w] : adj[v]) if (u != from) {
		addNode(u, v, w);
		dfs(u, v);
}}

#define sz(x) ssize(x)
void init(int root) {
	d.assign(sz(adj), 0);
	par.assign(sz(adj), root);
	jump = par;
	pval.assign(sz(adj), E);
	jval = pval;
	dfs(root, -1);
}

pair<int, T> lift(int u, int steps) {
	T ans = E;
	for (int target = max(d[u] - steps, 0); d[u] > target; ) {
		if (d[jump[u]] >= target) ans = comb(ans, jval[u]), u = jump[u];
		else ans = comb(ans, pval[u]), u = par[u];
	}
	return {u, ans};
}

pair<int, T> lca(int u, int v) {
	if (d[u] < d[v]) swap(u, v);
	T ans;
	tie(u, ans) = lift(u, d[u] - d[v]);
	while (u != v) {
		if (jump[u] != jump[v]) {
			ans = comb(comb(ans, jval[u]), jval[v]);
			u = jump[u], v = jump[v];
		} else {
			ans = comb(comb(ans, pval[u]), pval[v]);
			u = par[u], v = par[v];
		}
	}
	return {u, ans};
}

struct Union {
    vector<int> a;

    Union(int n) : a(n, -1) {}

    int find(int i) {
        return a[i] < 0 ? i : a[i] = find(a[i]);
    }

    bool join(int i, int j) {
        i = find(i);
        j = find(j);
        if (i == j) return false;
        a[j] = i;
        return true;
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int TT;
    cin >> TT;
    while (TT--) {
        int n, m;
        cin >> n >> m;
        vector<array<ll, 3>> edges(m);
        for (auto& [w, u, v] : edges) cin >> u >> v >> w, u--, v--;
        sort(all(edges));

        Union un(n);
        
        adj.assign(n, {});
        ll ans = 0;
        for (auto [w, u, v] : edges) {
            if (un.join(u, v)) {
                adj[u].emplace_back(v, w);
                adj[v].emplace_back(u, w);
                u = v = -1;
                ans += w;
            }
        }
        init(0);


        ll mn = 1e18;
        for (auto [w, u, v] : edges) if (u != -1) {
            auto [_, e] = lca(u, v);
            mn = min(mn, w - e[(w+1)%2]);
        }
        ll ans2 = mn > 1e17 ? -1 : ans + mn;
        if (ans % 2 == 1) swap(ans, ans2);

        cout << ans << ' ' << ans2 << '\n';
    }
}