#include<bits/stdc++.h>

using namespace std;

#define int long long

constexpr int inf = 1e18;

struct Edge {
    int u, v, w, id;
    bool operator<(const Edge A) const {
        return w <= A.w;
    }
};

void solve() {
    int n, m;
    cin >> n >> m;

    vector g(n + 1, vector<pair<int, int>>());
    vector<Edge> e;
    for (int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        e.push_back({u, v, w, i});
    }

    sort(e.begin(), e.end());
    vector<int> p(n + 1);
    iota(p.begin(), p.end(), 0);
    auto find = [&](auto self, int x) -> int {
        return x == p[x] ? x : p[x] = self(self, p[x]);
    };

    vector<bool> vis(m + 1, false);
    vector<int> ans(3, inf);
    ans[0] = 0;
    for (auto [u, v, w, id] : e) {
        int fx = find(find, u);
        int fy = find(find, v);
        if (fx == fy) continue;
        vis[id] = true;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
        ans[0] += w;
        p[fx] = fy;
    }

    int num = 0;
    for (int i = 1; i <= n; i++) {
        if (find(find, i) == i) num++;
    }

    if (num != 1) {
        cout << "-1 -1\n";
        return;
    }

    vector<int> dep(n + 1);
    vector f(n + 1, vector<int>(20));
    vector val(n + 1, vector<array<int, 2>>(20, {-inf, -inf}));
    auto dfs = [&](auto self, int u, int fa) -> void {
        f[u][0] = fa;
        dep[u] = dep[fa] + 1;
        for (auto [v, w] : g[u]) {
            if (v == fa) continue;
            if (w & 1) val[v][0][1] = w;
            else val[v][0][0] = w;
            self(self, v, u);
        }   
    };
    dfs(dfs, 1, 0);
    
    int opt;
    if (ans[0] & 1) ans[2] = ans[0], opt = 1;
    else ans[1] = ans[0], opt = 2;

    for (int j = 1; j <= 19; j++) {
        for (int i = 1; i <= n; i++) {
            f[i][j] = f[f[i][j - 1]][j - 1];
            for (int k = 0; k < 2; k++) {
                val[i][j][k] = max(val[i][j - 1][k], val[f[i][j - 1]][j - 1][k]);
            }
        }
    }

    auto Lca = [&](int u, int v) {
        if (dep[u] < dep[v]) swap(u, v);
        for (int i = 19; i >= 0; i--) {
            if (dep[f[u][i]] >= dep[v]) {
                u = f[u][i];
            }
        }
        if (u == v) return u;
        for (int i = 19; i >= 0; i--) {
            if (f[u][i] != f[v][i]) {
                u = f[u][i], v = f[v][i];
            }
        }
        return f[u][0];
    };

    for (auto [u, v, w, id] : e) {
        if (vis[id]) continue;
        int lca = Lca(u, v);
        int odd_mx = -inf, even_mx = -inf;
        for (int j = 19; j >= 0; j--) {
            if (dep[f[u][j]] >= dep[lca]) {
                even_mx = max(even_mx, val[u][j][0]);
                odd_mx = max(odd_mx, val[u][j][1]);
                u = f[u][j];
            }
        }
        if (w & 1) {
            ans[opt] = min(ans[opt], ans[0] + w - even_mx);
        }
        else ans[opt] = min(ans[opt], ans[0] + w - odd_mx);
    }
    if (ans[1] == inf) ans[1] = -1;
    if (ans[2] == inf) ans[2] = -1;
    cout << ans[1] << " " << ans[2] << "\n";
}

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

    int T = 1;
    cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}