#include <bits/stdc++.h>

using namespace std;

typedef long long i64;
typedef unsigned long long u64;
typedef double lf;

const int logn = 20;

int n, m;
vector< vector<pair<int, int>> > g;
vector< tuple<int, int, int> > edges;    
vector<int> dsu, rnk;
vector< vector< pair<int, int> > > tree;
vector<int> depth;
vector< vector<int> > jmp, mx[2];

int get(int v) {
    return dsu[v] == v ? v : dsu[v] = get(dsu[v]);
}

void unite(int u, int v) {
    u = get(u);
    v = get(v);
    if (rnk[u] < rnk[v]) {
        swap(u, v);
    }
    dsu[v] = u;
}

void dfs(int v, int p, int w) {
    depth[v] = p == -1 ? 0 : depth[p] + 1;
    jmp[0][v] = p;
    mx[0][0][v] = w % 2 == 0 ? w : -1;
    mx[1][0][v] = w % 2 == 1 ? w : -1;
    for (int i = 1; i < logn; i++) {
        int u = jmp[i - 1][v];
        if (u == -1) {
            jmp[i][v] = -1;
            mx[0][i][v] = mx[0][i - 1][v];
            mx[1][i][v] = mx[1][i - 1][v];
        } else {
            jmp[i][v] = jmp[i - 1][u];
            mx[0][i][v] = max(mx[0][i - 1][v], mx[0][i - 1][u]);
            mx[1][i][v] = max(mx[1][i - 1][v], mx[1][i - 1][u]);
        }
    }
    for (auto [u, ww] : tree[v]) {
        if (u == p) {
            continue;
        }
        dfs(u, v, ww);
    }
}

pair<int, int> jump(int v, int d) {
    int res = -1;
    for (int i = 0; i < logn; i++) {
        if (d & (1 << i)) {
            res = max(res, mx[0][i][v]);
            v = jmp[i][v];
        }
    }
    return {v, res};
}

int get_max(int u, int v, int x) {
    int du = depth[u];
    int dv = depth[v];
    if (du > dv) {
        swap(u, v);
        swap(du, dv);
    }
    auto [vv, ans] = jump(v, dv - du);
    v = vv;
    if (u == v) {
        return ans;
    }
    for (int i = logn - 1; i >= 0; i--) {
        if (jmp[i][u] != jmp[i][v]) {
            ans = max(ans, mx[x][i][u]);
            ans = max(ans, mx[x][i][v]);
            u = jmp[i][u];
            v = jmp[i][v];
        }
    }
    ans = max(ans, mx[x][0][u]);
    ans = max(ans, mx[x][0][v]);
    return ans;
}

void solve() {
    cin >> n >> m;
    g.assign(n, {});
    edges.clear();
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
        edges.emplace_back(w, u, v);
    }
    sort(edges.begin(), edges.end());
    dsu.assign(n, 0);
    iota(dsu.begin(), dsu.end(), 0);
    rnk.assign(n, 0);
    i64 w = 0;

    tree.assign(n, {});
    int spanning_size = 0;
    for (auto [ww, u, v] : edges) {
        if (get(u) != get(v)) {
            unite(u, v);
            // cerr << "TAKE " << u << ' ' << v << ' ' << ww << '\n';
            tree[u].emplace_back(v, ww);
            tree[v].emplace_back(u, ww);
            w += ww;
            spanning_size++;
        }
    }
    if (spanning_size != n - 1) {
        cout << "-1 -1\n";
        return;
    }
    jmp.assign(logn, vector<int>(n, -1));
    mx[0].assign(logn, vector<int>(n, -1));
    mx[1].assign(logn, vector<int>(n, -1));
    depth.assign(n, 0);
    dfs(0, -1, -1);

    vector<i64> ans(2);
    ans[w % 2] = w;
    const i64 inf = (i64)1e18;
    ans[1 - w % 2] = inf;

    for (auto [ww, u, v] : edges) {
        int x = get_max(u, v, 1 - ww % 2);
        // cerr << "GET " << u << ' ' << v << ' ' << ww << ' ' << x << '\n';
        if (x != -1) {
            ans[1 - w % 2] = min(ans[1 - w % 2], w - x + ww);
        }
    }
    if (ans[1 - w % 2] >= inf) {
        ans[1 - w % 2] = -1;
    }
    cout << ans[0] << ' ' << ans[1] << '\n';
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    int t = 1;
    cin >> t;
    for (int i = 0; i < t; i++) {
        solve();
    }
}