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

#define ll long long
#define PII pair<int, ll>
const ll N = 2e5 + 10, M = 5e5 + 10, inf = 0x3f3f3f3f;
ll n, m, p[N];
struct edge {
    ll a, b, w;
    bool operator<(const edge& a) const { return this->w < a.w; }
};

ll find(ll x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void solve()
{
    cin >> n >> m;
    vector<edge> ed(m + 1);
    for (int i = 1; i <= m; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        ed[i] = {a, b, c};
    }
    sort(ed.begin() + 1, ed.end());
    for (int i = 1; i <= n; i++) p[i] = i;
    unordered_set<ll> st;
    vector<vector<PII>> G(n + 1);
    ll res = 0;
    for (int i = 1; i <= m; i++) {
        ll x = ed[i].a, y = ed[i].b, z = ed[i].w;
        if (find(x) != find(y)) {
            p[find(x)] = find(y);
            res += z;
            st.insert(i);
        }
    }

    if (st.size() < n - 1) {
        cout << -1 << " " << -1 << endl;
        return;
    }

    for (int i = 1; i <= m; i++) {
        if (st.count(i)) {
            ll x = ed[i].a, y = ed[i].b, z = ed[i].w;
            G[x].push_back({y, z}), G[y].push_back({x, z});
        }
    }

    vector<vector<int>> fa(n + 1, vector<int>(31));
    vector<vector<vector<ll>>> F(2, vector<vector<ll>>(n + 1, vector<ll>(31)));
    vector<int> dep(n + 1);

    auto dfs = [&](auto dfs, int u, int f, ll fw) -> void {
        if (fw & 1) {
            F[1][u][0] = fw;
        }
        else {
            F[0][u][0] = fw;
        }
        fa[u][0] = f;
        dep[u] = dep[f] + 1;
        for (int i = 1; i < 31; i++) {
            fa[u][i] = fa[fa[u][i - 1]][i - 1];
            F[1][u][i] = max(F[1][fa[u][i - 1]][i - 1], F[1][u][i - 1]);
            F[0][u][i] = max(F[0][fa[u][i - 1]][i - 1], F[0][u][i - 1]);
        }
        for (auto [v, w] : G[u]) {
            if (v != f) {
                dfs(dfs, v, u, w);
            }
        }
    };

    auto get = [&](int x, int y, int idx) -> ll {
        if (dep[x] < dep[y]) {
            swap(x, y);
        }
        int d = dep[x] - dep[y];
        ll tmp = 0;
        for (int i = 0; (1 << i) <= d; i++) {
            if ((d >> i) & 1) {
                tmp = max(tmp, F[idx][x][i]);
                x = fa[x][i];
            }
        }
        if (x == y) return tmp;
        for (int i = log2(dep[y]); i >= 0; i--) {
            if (fa[x][i] != fa[y][i]) {
                tmp = max(tmp, F[idx][y][i]);
                tmp = max(tmp, F[idx][x][i]);
                x = fa[x][i];
                y = fa[y][i];
            }
        }
        return max({tmp, F[idx][x][0], F[idx][y][0]});
    };

    dfs(dfs, 1, 0, 0);

    ll ans = 1e18;

    for (int i = 1; i <= m; i++) {
        if (!st.count(i)) {
            auto [u, v, w] = ed[i];
            ll t = get(u, v, 1 - (w & 1ll));
            ans = min(res - t + w, ans);
        }
    }
    if (ans == 1e18) ans = -1;
    if (res & 1) {
        cout << ans << " " << res << endl;
    }
    else {
        cout << res << " " << ans << endl;
    }
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}