#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

struct P {
    int x, y, z;
};

inline void Solve() {
    int n, m;
    cin >> n >> m;
    vector<P>edg;
    for (int i = 1, x, y, z; i <= m; i++) {
        cin >> x >> y >> z;
        edg.push_back({x, y, z});
    }
    sort(edg.begin(), edg.end(), [](const P&x, const P&y) {
        return x.z < y.z;
    });
    vector<int>fa(n + 1);
    for (int i = 1; i <= n; i++) fa[i] = i;
    auto find = [&fa] (auto &&find, const int&x) -> int {
        if (x == fa[x]) return x;
        return fa[x] = find(find, fa[x]);
    };
    int cnt = 0, ans = 0;
    vector<vector<pair<int, int>>> g(n + 1);
    vector<bool> vis(m + 1);
    for (int fx, fy, i = 0; auto &[x, y, z] : edg) {
        i += 1;
        fx = find(find, x), fy = find(find, y);
        if (fx == fy) continue;
        fa[fx] = fy;
        vis[i - 1] = 1;
        g[x].push_back({y, z});
        g[y].push_back({x, z});
        ans += z;
        if (++cnt == n - 1) break;
    }
    if (cnt != n - 1) {
        cout << "-1 -1" << endl;
        return;
    }
    vector<vector<int>>f(n + 1, vector<int>(20));
    vector<vector<vector<int>>>mx(2, f);
    vector<int> dep(n + 1, 0);
    auto dfs = [&] (auto &&dfs, const int &x, const int &fa) -> void {
        f[x][0] = fa;
        dep[x] = dep[fa] + 1;
        for (auto [y, z] : g[x]) {
            if (y == fa) continue;
            mx[z & 1][y][0] = z;
            dfs(dfs, y, x);
        }
    };
    dfs(dfs, 1, 0);
    for (int j = 1; j <= 19; j++) {
        for (int i = 1; i <= n; i++) {
            f[i][j] = f[f[i][j - 1]][j - 1];
            mx[0][i][j] = max(mx[0][i][j - 1], mx[0][f[i][j-1]][j-1]);
            mx[1][i][j] = max(mx[1][i][j - 1], mx[1][f[i][j-1]][j-1]);
        }
    }

    auto LCA = [&](int x, int y, int odd) -> pair<int, int> {
        int maxn = -1;
        if (dep[y] > dep[x]) swap(x, y);
        for (int i = 19; i >= 0; i--) {
            if (dep[f[x][i]] >= dep[y]) {
                maxn = max(maxn, mx[odd][x][i]);
                x = f[x][i];
            }
        }
        if (x == y) return {x, maxn};
        for (int i = 19; i >= 0; i--) {
            if (f[x][i] != f[y][i]) {
                maxn = max(maxn, mx[odd][x][i]);
                maxn = max(maxn, mx[odd][y][i]);
                x = f[x][i];
                y = f[y][i];
            }
        }
        maxn = max(maxn, mx[odd][x][0]);
        maxn = max(maxn, mx[odd][y][0]);
        return {f[x][0], maxn};
    };
    int res[2];
    res[0] = res[1] = 1000000000000000000;
    res[ans & 1] = ans;
    for (int id = 0; auto [x, y, z] : edg) {
        if (vis[id++]) continue;
        auto [lca, mx] = LCA(x, y, z & 1 ^ 1);
        if (mx == -1) continue;
        int t = ans - mx + z;
        res[t & 1] = min(res[t & 1], t);
    }
    for (int i = 0; i < 2; i++) if (res[i] == 1000000000000000000) res[i] = -1;
    cout << res[0] << " " << res[1] << endl;


}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) {
        Solve();
    }
    return 0;
}

/*
1
7 8
1 2 1 
1 3 1 
1 4 1
2 5 2
2 6 4
6 7 2
1 5 6
1 7 3
*/