#include <bits/stdc++.h>

struct DSU {
    std::vector<int> fa;
    explicit DSU(int n) : fa(n) {
        std::iota(fa.begin(), fa.end(), 0);
    }
    int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        fa[x] = y;
        return true;
    }
};

using i64 = int64_t;
constexpr i64 INF = 1e18;
constexpr int MAXN = 2e5 + 19, MAXB = 20;
int fa[MAXN][MAXB], max[MAXN][MAXB];

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

    std::vector<std::pair<int, std::pair<int, int>>> edges;
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        edges.emplace_back(w, std::pair<int, int>{u, v});
    }
    std::sort(edges.begin(), edges.end());

    i64 W = 0;
    int edge_num = 0;
    DSU dsu(n + 1);
    std::vector<std::vector<std::pair<int, int>>> T(n + 1);
    for (auto [w, p] : edges) {
        auto [u, v] = p;
        if (dsu.merge(u, v)) {
            T[u].emplace_back(v, w);
            T[v].emplace_back(u, w);
            W += w;
            edge_num += 1;
        }
    }

    if (edge_num < n - 1) {
        std::cout << "-1 -1\n";
        return;
    }

    std::vector<int> dep(n + 1);
    auto dfs = [&](auto self, int node, int f, int w) -> void {
        dep[node] = dep[f] + 1;
        fa[node][0] = f;
        max[node][0] = w;
        for (int i = 1; i < MAXB; ++i) {
            fa[node][i] = fa[fa[node][i - 1]][i - 1];
            max[node][i] = std::max(max[node][i - 1], max[fa[node][i - 1]][i - 1]);
        }
        
        for (auto [to, w] : T[node]) {
            if (to == f) {
                continue;
            }
            self(self, to, node, w);
        }
    };
    dfs(dfs, 1, 0, 0);

    auto get_max = [&](int u, int v) -> int {
        if (dep[u] < dep[v]) {
            std::swap(u, v);
        }
        int res = 0;
        for (int i = MAXB - 1; i >= 0; --i) {
            if (dep[fa[u][i]] >= dep[v]) {
                res = std::max(res, max[u][i]);
                u = fa[u][i];
            }
        }
        if (u == v) {
            return res;
        }
        for (int i = MAXB - 1; i >= 0; --i) {
            if (fa[u][i] != fa[v][i]) {
                res = std::max(res, max[u][i]);
                u = fa[u][i];
                res = std::max(res, max[v][i]);
                v = fa[v][i];
            }
        }
        return std::max({res, max[u][0], max[v][0]});
    };

    i64 min_odd = INF, min_even = INF;
    for (auto [w, p] : edges) {
        auto [u, v] = p;

        i64 res = W + w - get_max(u, v);
        if (res & 1) {
            min_odd = std::min(min_odd, res);
        } else {
            min_even = std::min(min_even, res);
        }
    }

    if (min_odd == INF) {
        min_odd = -1;
    }
    if (min_even == INF) {
        min_even = -1;
    }

    std::cout << min_even << ' ' << min_odd << '\n';
}

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

    int t;
    std::cin >> t;

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