#include <bits/stdc++.h>

using ll = long long;
using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    // vector<vector<pair<int, int>>> adj(n);
    // for (int i = 0; i < n - 1; i++) {
    //     int u, v, w;
    //     cin >> u >> v >> w;
    //     u--, v--;
    //     adj[u].emplace_back(v, w);
    //     adj[v].emplace_back(u, w);
    // }
    vector<tuple<int, int, int>> edge(m);
    vector<bool> chose(m);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        edge[i] = {w, u, v};
    }
    sort(edge.begin(), edge.end());

    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    auto find = [&](int x) {
        while (x != p[x]) {
            x = p[x] = p[p[x]];
        }
        return x;
    };

    vector<vector<pair<int, int>>> adj(n);
    ll sum = 0;
    for (int i = 0; i < m; i++) {
        auto [w, u, v] = edge[i];
        int x = find(u), y = find(v);
        if (x != y) {
            sum += w;
            p[y] = x;
            adj[u].emplace_back(v, w);
            adj[v].emplace_back(u, w);
            chose[i] = true;
        }
    }

    for (int i = 0; i < n; i++) {
        if (find(i) != find(0)) {
            cout << -1 << " " << -1 << endl;
            return;
        }
    }

    vector<array<int, 20>> fa(n);
    vector<array<array<int, 20>, 2>> we(n);
    memset(fa.data(), 0, n * sizeof (array<int, 20>));
    memset(we.data(), 0, n * sizeof (array<array<int, 20>, 2>));
    vector<int> dep(n);
    auto dfs = [&](auto &&self, int u) -> void {
        for (int i = 1; i < 20; i++) {
            fa[u][i] = fa[fa[u][i - 1]][i - 1];
            we[0][u][i] = max(we[0][u][i - 1], we[0][fa[u][i - 1]][i - 1]);
            we[1][u][i] = max(we[1][u][i - 1], we[1][fa[u][i - 1]][i - 1]);
        }
        for (auto [v, w] : adj[u]) {
            if (v != fa[u][0]) {
                we[w & 1][v][0] = w;
                fa[v][0] = u;
                dep[v] = dep[u] + 1;
                self(self, v);
            }
        }
    };
    dfs(dfs, 0);

    auto LCA = [&](int x, int y, int k) {
        if (dep[x] < dep[y]) {
            swap(x, y);
        }
        int ans = 0;
        for (int i = 19; i >= 0; i--) {
            if (dep[fa[x][i]] >= dep[y]) {
                ans = max(ans, we[k][x][i]);
                x = fa[x][i];
            }
        }
        if (x == y) return ans;
        for (int i = 19; i >= 0; i--) {
            if (fa[x][i] != fa[y][i]) {
                ans = max(ans, we[k][x][i]);
                ans = max(ans, we[k][y][i]);
                x = fa[x][i];
                y = fa[y][i];
            }
        }
        return max(ans, max(we[k][y][0], we[k][x][0]));
    };

    ll ans = 1e18;
    for (int i = 0; i < m; i++) {
        if (!chose[i]) {
            auto [w, x, y] = edge[i];
            int res = LCA(x, y, ~w & 1);
            if (res != 0) {
                ans = min(ans, sum - res + w);
            }
        }
    }
    if (sum & 1) {
        cout << ((ans == 1e18) ? -1 : ans) << " " << sum << endl;
    } else {
        cout << sum << " " << ((ans == 1e18) ? -1 : ans) << endl;
    }
}

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

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

    return 0;
}