// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return b < a ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 200005;
const int MAXM = 500005;
const int MAXL = 20;

int t;
int n, m;
iii eg[MAXM];
bool todo[MAXM];
vii adj[MAXN];

struct Jump {
    int v, mx[2];
    Jump(): v(0) {
        mx[0] = mx[1] = -INF;
    }
    Jump operator+(const Jump &o) const {
        Jump res = *this;
        mxto(res.mx[0], o.mx[0]);
        mxto(res.mx[1], o.mx[1]);
        return res;
    }
} p[MAXL][MAXN];

int l[MAXN];
void dfs(int u) {
    REP (k, 1, MAXL) {
        p[k][u] = p[k - 1][p[k - 1][u].v] + p[k - 1][u];
    }
    for (auto [v, w] : adj[u]) {
        if (v == p[0][u].v) {
            continue;
        }
        p[0][v].v = u;
        p[0][v].mx[w & 1] = w;
        p[0][v].mx[w & 1 ^ 1] = -INF;
        l[v] = l[u] + 1;
        dfs(v);
    }
}
Jump get_path(int a, int b) {
    if (l[a] < l[b]) {
        swap(a, b);
    }
    Jump ja, jb;
    ja.v = a; jb.v = b;
    RREP (k, MAXL - 1, 0) {
        if (p[k][ja.v].v && l[p[k][ja.v].v] >= jb.v) {
            ja = p[k][ja.v] + ja;
        }
    }
    if (a == b) {
        return ja;
    }
    RREP (k, MAXL - 1, 0) {
        if (p[k][ja.v].v != p[k][jb.v].v) {
            ja = p[k][ja.v] + ja;
            jb = p[k][jb.v] + jb;
        }
    }
    return p[0][ja.v] + ja + p[0][jb.v] + jb;
}

struct DSU {
    int n, comp;
    vector<int> p, rnk;
    DSU(int n): n(n), comp(n), p(n + 1, 0), rnk(n + 1, 0) {
        iota(p.begin(), p.end(), 0);
    }
    int findp(int i) {
        if (p[i] == i) {
            return i;
        }
        return p[i] = findp(p[i]);
    }
    bool join(int a, int b) {
        int pa = findp(a), pb = findp(b);
        if (pa == pb) {
            return 0;
        }
        if (rnk[pa] < rnk[pb]) {
            swap(pa, pb);
        }
        if (rnk[pa] == rnk[pb]) {
            rnk[pa]++;
        }
        p[pb] = pa;
        comp--;
        return 1;
    }
};

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> t;
    while (t--) {
        cin >> n >> m;
        REP (i, 1, n + 1) {
            adj[i].clear();
        }
        REP (i, 0, m) {
            int u, v, w; cin >> u >> v >> w;
            eg[i] = {w, u, v};
            todo[i] = 0;
        }
        DSU dsu(n);
        ll base = 0;
        REP (i, 0, m) {
            auto [w, u, v] = eg[i];
            if (dsu.join(u, v)) {
                adj[u].pb({v, w});
                adj[v].pb({u, w});
                base += w;
            } else {
                todo[i] = 1;
            }
        }
        if (dsu.comp != 1) {
            cout << -1 << ' ' << -1 << '\n';
            continue;
        }
        ll ans[2] = {LINF, LINF};
        ans[base & 1] = base;
        dfs(1);
        REP (i, 0, m) {
            if (todo[i]) {
                auto [w, u, v] = eg[i];
                Jump res = get_path(u, v);
                int rmv = res.mx[w & 1 ^ 1];
                if (rmv != -INF) {
                    mnto(ans[base & 1 ^ 1], base + w - rmv);
                }
            }
        }
        REP (b, 0, 2) {
            if (ans[b] == LINF) {
                ans[b] = -1;
            }
            cout << ans[b] << ' ';
        }
        cout << '\n';
    }
    return 0;
}