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

const int MAXN = 200005;
const int LOGN = 20;

struct Edge {
    int u, v;
    int64_t w;
    bool in_mst;
};

int T, n, m;
int parent[MAXN][LOGN], depth[MAXN];
int64_t max_edge[MAXN][LOGN];
vector<pair<int, int64_t>> tree[MAXN];
vector<Edge> edges;

int find_set(vector<int>& dsuf, int u) {
    if (dsuf[u] != u)
        dsuf[u] = find_set(dsuf, dsuf[u]);
    return dsuf[u];
}

void union_sets(vector<int>& dsuf, int u, int v) {
    u = find_set(dsuf, u);
    v = find_set(dsuf, v);
    if (u != v)
        dsuf[u] = v;
}

void dfs(int u, int p, int64_t w) {
    parent[u][0] = p;
    max_edge[u][0] = w;
    depth[u] = depth[p] + 1;
    for (int k = 1; k < LOGN; ++k) {
        parent[u][k] = parent[parent[u][k - 1]][k - 1];
        max_edge[u][k] = max(max_edge[u][k - 1], max_edge[parent[u][k - 1]][k - 1]);
    }
    for (auto& [v, weight] : tree[u]) {
        if (v != p) {
            dfs(v, u, weight);
        }
    }
}

int64_t query_max(int u, int v) {
    if (depth[u] < depth[v])
        swap(u, v);
    int64_t res = 0;
    for (int k = LOGN - 1; k >= 0; --k) {
        if (depth[parent[u][k]] >= depth[v]) {
            res = max(res, max_edge[u][k]);
            u = parent[u][k];
        }
    }
    if (u == v)
        return res;
    for (int k = LOGN - 1; k >= 0; --k) {
        if (parent[u][k] != parent[v][k]) {
            res = max({res, max_edge[u][k], max_edge[v][k]});
            u = parent[u][k];
            v = parent[v][k];
        }
    }
    res = max({res, max_edge[u][0], max_edge[v][0]});
    return res;
}

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

    cin >> T;
    while (T--) {
        cin >> n >> m;
        edges.clear();
        for (int i = 0; i <= n; ++i)
            tree[i].clear();

        for (int i = 0; i < m; ++i) {
            int u, v;
            int64_t w;
            cin >> u >> v >> w;
            edges.push_back({u, v, w, false});
        }

        // Kruskal's algorithm to build MST
        vector<int> dsuf(n + 1);
        iota(dsuf.begin(), dsuf.end(), 0);
        sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
            return a.w < b.w;
        });
        int64_t cost_mst = 0;
        for (auto& e : edges) {
            int u = find_set(dsuf, e.u);
            int v = find_set(dsuf, e.v);
            if (u != v) {
                union_sets(dsuf, u, v);
                e.in_mst = true;
                cost_mst += e.w;
                tree[e.u].emplace_back(e.v, e.w);
                tree[e.v].emplace_back(e.u, e.w);
            }
        }

        // Initialize LCA structures
        depth[0] = -1;
        dfs(1, 0, 0);

        int64_t min_delta_odd = INT64_MAX;
        int64_t min_delta_even = INT64_MAX;

        for (auto& e : edges) {
            if (!e.in_mst) {
                int64_t max_w = query_max(e.u, e.v);
                int64_t delta = e.w - max_w;
                if (delta < 0)
                    continue; // Not possible
                if (delta % 2 == 1) {
                    min_delta_odd = min(min_delta_odd, delta);
                } else {
                    min_delta_even = min(min_delta_even, delta);
                }
            }
        }

        int64_t T1 = -1, T2 = -1;
        if (cost_mst % 2 == 0) {
            T1 = cost_mst;
            if (min_delta_odd != INT64_MAX) {
                T2 = cost_mst + min_delta_odd;
            }
        } else {
            T2 = cost_mst;
            if (min_delta_odd != INT64_MAX) {
                T1 = cost_mst + min_delta_odd;
            }
        }
        cout << T1 << ' ' << T2 << '\n';
    }
    return 0;
}