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

using is = int32_t;
using il = int64_t;
using us = uint32_t;
using ul = uint64_t;

template<class T> void mes(T *arr, us n=1, us b=0) { memset(arr, b, n*sizeof(T)); }

template<us LEN>
struct DSU {
    us far[LEN] = {0}, rnk[LEN] = {0};
    void init(us l, us r) {
        mes(rnk+l, r-l);
        iota(far+l, far+r, l);
    }
    us find(us u) {
        if(far[u]==u) return u;
        else return far[u] = find(far[u]);
    }
    bool same(us l, us r) { return find(l) == find(r); }
    bool merge(us l, us r) {
        if((l=find(l))==(r=find(r))) return 0;
        if(rnk[l]<rnk[r]) swap(l, r);
        else if(rnk[l]==rnk[r]) ++rnk[l];
        return far[r]=l, 1;
    }
};
// -------------------------
con us MXN = 2e5 + 7;
con us MXM = 5e5 + 7;
con us LGM = 20;

us n, m;
// (w, u, v)
array<us, 3> inp[MXM];
DSU<MXN> dsu;

// (v, w)
using EI = array<us, 2>;
vector<EI> g[MXN];

us dpt[MXN], far[MXN][LGM], mxl[MXN][LGM][2];

void dfs(us u, us f=0) {
    for(us i=1; i<LGM; ++i) {
        far[u][i] = far[far[u][i-1]][i-1];
        mxl[u][i][0] = max(mxl[u][i-1][0], mxl[far[u][i-1]][i-1][0]);
        mxl[u][i][1] = max(mxl[u][i-1][1], mxl[far[u][i-1]][i-1][1]);
    }

    for(auto [v, w]:g[u]) if(v!=f) {
        dpt[v] = dpt[u] + 1;
        far[v][0] = u;
        mxl[v][0][w&1] = w;
        dfs(v, u);
    }
}

us get_far(us u, us d) {
    for(us i=0; d&&i<LGM; ++i, (d>>=1))
        if(d&1) u = far[u][i];
    return u;
}

us get_lca(us l, us r) {
    if(dpt[l]<dpt[r]) swap(l, r);
    l = get_far(l, dpt[l]-dpt[r]);
    if(l==r) return l;
    for(us i=LGM; i--;) {
        if(far[l][i]!=far[r][i]) {
            l = far[l][i];
            r = far[r][i];
        }
    }
    return far[l][0];
}

us get_mxl(us u, us d, bool odd) {
    us res = 0;
    for(us i=0; d&&i<LGM; ++i, (d>>=1)) {
        if(d&1) {
            res = max(res, mxl[u][i][odd]);
            u = far[u][i];
        }
    }
    return res;
}

ul ans[2];

void solve() {
    bool fg = ans[0]>0;
    if(!ans[!fg]) {
        cout << "-1 -1";
        return;
    }

    for(us i=0; i<m; ++i) {
        auto & [w, u, v] = inp[i];
        if(w) {
            us lca = get_lca(u, v);
            us tw = max(get_mxl(u, dpt[u]-dpt[lca], !(w&1)),
                        get_mxl(v, dpt[v]-dpt[lca], !(w&1)));
            if(tw) {
                ans[fg] = max(ans[fg], ans[!fg]+(w-tw));
            }
        }
    }

    if(ans[fg]==0) ans[fg] = -1;
    cout << il(ans[0]) << ' ' << il(ans[1]);
}

void pre() {
    cin >> n >> m;
    for(us i=0, u, v, w; i<m; ++i) {
        cin >> u >> v >> w;
        inp[i] = {w, --u, --v};
    }
    sort(inp, inp+m);
    us cnt = 0;
    dsu.init(0, n);
    ul res = 0;
    for(us i=0; i<m; ++i) {
        auto & [w, u, v] = inp[i];
        if(dsu.merge(u, v)) {
            res += w;
            g[u].push_back({v, w});
            g[v].push_back({u, w});
            w = 0; ++cnt;
        }
    }
    if(cnt==n-1)
        ans[res&1] = res;

    dfs(0);
}

void aft() {
    for(us i=0; i<n; ++i)
        g[i].clear();
    ans[0] = ans[1] = 0;
    cout << '\n';
}

us _t = 1;
void init() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> _t;
}

int main() {
    init();
    for(us i=1; i<=_t;) {
        pre(); solve();
        ++i<=_t?aft():exit(0);
    }
}