#include <bits/stdc++.h>

using namespace std;

using ll = long long;
constexpr ll inf = 1e18;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<array<int, 3>> es(m + 1);
    for(int i = 1; i <= m; i++) {
        cin >> es[i][0] >> es[i][1] >> es[i][2];
    }
    sort(es.begin() + 1, es.end(), [&](array<int, 3> a, array<int, 3> b) {
        return a[2] < b[2];
    });
    vector<int> fa(n + 1);
    iota(fa.begin(), fa.end(), 0);
    function<int(int)> find = [&](int x) {
        return x == fa[x] ? x : fa[x] = find(fa[x]);
    };
    vector<int> sel(m + 1);
    vector G(n + 1, vector<pair<int, int>>());
    vector<ll> ans(2); ans[1] = inf;
    for(int i = 1; i <= m; i++) {
        auto [u, v, w] = es[i];
        if(find(u) != find(v)) {
            sel[i] = 1;
            fa[find(u)] = find(v);
            G[u].push_back({v, w});
            G[v].push_back({u, w});
            ans[0] += w;
        }
    }
    for(int i = 1; i <= n; i++) {
        if(find(i) != find(1)) {
            cout << "-1 -1\n";
            return;
        }
    }
    vector f(n + 1, vector(20, array<int, 3>())); // <fa, max0, max1>
    vector<int> dep(n + 1);
    auto dfs = [&](auto self, int x, int fz) -> void {
        dep[x] = dep[fz] + 1;
        for(int i = 1; i < 20; i++) {
            int t = f[x][i - 1][0];
            f[x][i][0] = f[t][i - 1][0];
            f[x][i][1] = max(f[x][i - 1][1], f[t][i - 1][1]);
            f[x][i][2] = max(f[x][i - 1][2], f[t][i - 1][2]);
        }
        for(auto [y, w] : G[x]) {
            if(y != fz) {
                f[y][0] = {x, w % 2 ? -1 : w, w % 2 ? w : -1};
                self(self, y, x);
            }
        }
    };
    f[1][0] = {1, -1, -1};
    dfs(dfs, 1, 0);
    for(int i = 1; i <= m; i++) if(!sel[i]) {
        auto [x, y, w] = es[i];
        if(dep[x] < dep[y]) swap(x, y);
        // cerr << x << ' ' << y << ' ' << w << ' ';
        int now = 0, ty = w % 2 ? 1 : 2;
        for(int j = 19; ~j; j--) {
            if(dep[f[x][j][0]] >= dep[y]) {
                now = max(now, f[x][j][ty]);
                x = f[x][j][0];
            }
        }
        // cerr << x << ' ' << y << ' ' << w << ' ';
        if(x != y) {
            for(int j = 19; ~j; j--) {
                if(f[x][j][0] != f[y][j][0]) {
                    now = max({now, f[x][j][ty], f[y][j][ty]});
                    x = f[x][j][0], y = f[y][j][0];
                }
            }
            now = max({now, f[x][0][ty], f[y][0][ty]});
        }
        // cerr << now << '\n';
        if(now != -1) ans[1] = min(ans[1], ans[0] + w - now);
    }
    if(ans[1] == inf) ans[1] = -1;
    if(ans[0] % 2) swap(ans[0], ans[1]);
    cout << ans[0] << ' ' << ans[1] << '\n';
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) solve();
    return 0;
}
/*
3
2 1
1 2 5
3 1
1 3 1
4 4
1 2 1
1 3 1
1 4 1
2 4 2

*/