// https://www.youtube.com/watch?v=R0P_f0gXXqs
// I could feel your heartbeat
// I could feel somewhere you’re looking down
// ‘Cause it’s you who I’m loving
// And it’s you that I want in need

#ifndef ONLINE_JUDGE
#include "templates/debug.hpp"
#else
#define debug(...)
#endif

#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using u64 = uint64_t;

class UnionFindSet {
    vector<int> fa, sz;

  public:
    UnionFindSet(int n) : fa(n), sz(n, 1) {
        for (int i = 0; i < n; i++) {
            fa[i] = i;
        }
    }

    int size(int x) { return sz[find(x)]; }

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

    int merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return 0;
        if (sz[x] < sz[y]) swap(x, y);
        fa[y] = x, sz[x] += sz[y];
        return 1;
    }
};

#define int i64
constexpr int INF = 1e18;
void solve() {
    int n, m; cin >> n >> m;
    struct Edge {
        int u, v, w; 
        bool operator < (const Edge& e) const {
            return w < e.w;
        }
    };
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        edges[i].u--, edges[i].v--;
    }
    sort(edges.begin(), edges.end());
    vector<vector<pair<int, int>>> adj(n);
    UnionFindSet ufs(n);
    int te = 0, s0 = 0;
    for (auto [u, v, w]: edges) {
        if (ufs.merge(u, v)) {
            adj[u].emplace_back(v, w);
            adj[v].emplace_back(u, w);
            te++; s0 += w;
        }
    }
    if (te < n - 1) {
        cout << -1 << " " << -1 << "\n";
        return;
    }
    array<int, 2> ans = {-1, -1};
    ans[s0 % 2] = s0;
    vector<vector<int>> fa(20, vector<int>(n));
    array<vector<vector<int>>, 2> mx;
    mx.fill(vector(20, vector<int>(n, -INF)));
    vector<int> dep(n);
    function<void(int, int)> dfs = [&](int u, int p) {
        for (int b = 1; b < 20; b++) {
            fa[b][u] = fa[b - 1][fa[b - 1][u]];
            mx[0][b][u] = max(mx[0][b - 1][u], mx[0][b - 1][fa[b - 1][u]]);
            mx[1][b][u] = max(mx[1][b - 1][u], mx[1][b - 1][fa[b - 1][u]]);
        }
        for (auto [v, w]: adj[u]) {
            if (v == p) continue;
            fa[0][v] = u;
            mx[w % 2][0][v] = w;
            dep[v] = dep[u] + 1;
            dfs(v, u);
        }
    };
    dfs(0, 0);
    auto ancestor = [&](int u, int diff) {
        for (int b = 19; b >= 0; b--) {
            if (diff >> b & 1) u = fa[b][u];
        }
        return u;
    };
    auto anc_query = [&](int u, int diff, int o) {
        int res = -INF;
        for (int b = 19; b >= 0; b--) {
            if (diff >> b & 1) {
                res = max(res, mx[o][b][u]);
                u = fa[b][u];
            }
        }
        return res;
    };
    auto lca = [&] (int u, int v) {
        if (dep[u] < dep[v]) swap(u, v);
        u = ancestor(u, dep[u] - dep[v]);
        if (u == v) return u;
        for (int b = 19; b >= 0; b--) {
            if (fa[b][u] != fa[b][v]) {
                u = fa[b][u];
                v = fa[b][v];
            }
        }
        return fa[0][u];
    };
    int min_diff = INF;
    for (auto [u, v, w]: edges) {
        int l = lca(u, v), o = w % 2;
        int ans = -INF;
        ans = max(ans, anc_query(u, dep[u] - dep[l], o ^ 1));
        ans = max(ans, anc_query(v, dep[v] - dep[l], o ^ 1));
        if (ans != -INF) {
            min_diff = min(min_diff, w - ans);
        }
    }
    if (min_diff != INF) ans[(s0 & 1) ^ 1] = s0 + min_diff;
    cout << ans[0] << " " << ans[1] << "\n";

}
#undef int

// Make bold hypotheses and verify carefully
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    };
}