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

struct DSU {
    int n;
    vector<int> fa;

    DSU (int n) : n(n) {
        fa.resize(n);
        iota(fa.begin(), fa.end(), 0);
    }

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

    void merge(int x, int y) {
        int fx = find(x);
        int fy = find(y);

        fa[fy] = fx;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

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

    DSU dsu(n);

    vector<vector<array<int, 2>>> e(n);
    int cnt = 0;
    vector<array<int, 3>> a;
    LL sum = 0;

    vector<array<int, 3>> ee(m);

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        ee[i] = {w, u, v};
    }

    sort(ee.begin(), ee.end());
    for (int i = 0; i < m; ++i) {
        auto [z, x, y] = ee[i];
        --x, --y;

        if (dsu.same(x, y)) {
            a.push_back({x, y, z});
            continue;
        }

        e[x].push_back({y, z});
        e[y].push_back({x, z});
        dsu.merge(x, y);
        ++cnt;
        sum += z;
    }

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

    const int INF = 1e9 + 10;
    const LL INF1 = 1e18 + 10;
    
    const int N = __lg(n) + 1;
    vector fa(N, vector<int>(n));
    vector val(2, vector(N, vector<int>(n, INF)));
    vector<int> dep(n);
    
    auto dfs = [&](auto &&self, int u) -> void {
        for (auto [v, w]: e[u]) {
            if (v == fa[0][u]) {
                continue;
            }
            dep[v] = dep[u] + 1;
            val[w & 1][0][v] = w;
            fa[0][v] = u;
            self(self, v);
        }
    };

    dep[0] = 1;
    dfs(dfs, 0);

    for (int i = 1; i < N; ++i) {
        for (int j = 0; j < n; ++j) {
            fa[i][j] = fa[i - 1][fa[i - 1][j]];
            val[0][i][j] = min(val[0][i - 1][j], val[0][i - 1][fa[i - 1][j]]);
            val[1][i][j] = min(val[1][i - 1][j], val[1][i - 1][fa[i - 1][j]]);
        }
    }

    LL sum1 = INF1;
    for (auto [u, v, w] : a) {
        int t = w & 1;
        int tt = 1 - t;

        if (dep[u] < dep[v]) {
            swap(u, v);
        }

        int res = INF;
        for (int i = N - 1; i >= 0; --i) {
            if (fa[i][u] != -1 && dep[fa[i][u]] >= dep[v]) {
                u = fa[i][u];
                res = min(res, val[tt][i][u]);
            }
        }

        for (int i = N - 1; i >= 0; --i) {
            if (fa[i][u] != fa[i][v]) {
                res = min({res, val[tt][i][u], val[tt][i][v]});
                u = fa[i][u];
                v = fa[i][v];
            }
        }

        res = min({res, val[tt][0][u], val[tt][0][v]});

        if (res != INF) {
            sum1 = min(sum1, sum - res + w);
        }
    }

    if (sum != INF1 && (sum % 2 == 0)) {
        cout << sum << ' ';
    } else if (sum1 != INF1 && (sum1 % 2 == 0)) {
        cout << sum1 << ' ';
    } else {
        cout << -1 << ' ';
    }

    if (sum != INF1 && (sum % 2 == 1)) {
        cout << sum << '\n';
    } else if (sum1 != INF1 && (sum1 % 2 == 1)) {
        cout << sum1 << '\n';
    } else {
        cout << -1 << '\n';
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}