#include <bits/stdc++.h>

using namespace std;

#define Endl '\n'
#define ll long long
#define int ll
#define ls first
#define rs second
#define pii pair<int, int>
#define pb push_back
const int N = 2e5 + 3;
const int LOGN = 19;
const int INF = 2e9;
ll n, m;
ll pre[N];
ll dep[N];
ll odd[LOGN + 1][N], even[LOGN + 1][N];
ll fa[LOGN + 1][N];
vector<array<ll, 3>> E;
vector<pii> e[N];
map<pii, ll> mp;
void init(int n)
{
    for (int i = 1; i <= n; i++) {
        pre[i] = i;
    }
}
int find(int x)
{
    if (pre[x] == x) {
        return x;
    }
    return pre[x] = find(pre[x]);
}
bool join(int x, int y)
{
    int fx = find(x), fy = find(y);
    if (fx != fy) {
        pre[fx] = fy;
        return 1;
    }
    return 0;
}
void dfs(int u, int f)
{
    dep[u] = dep[f] + 1;
    for (auto [v, w] : e[u]) {
        if (v == f)
            continue;
        if (w & 1) {
            odd[0][v] = w;
            even[0][v] = 0;
        } else {
            odd[0][v] = 0;
            even[0][v] = w;
        }
        fa[0][v] = u;
        dfs(v, u);
    }
}
pii LCA(int u, int v)
{
    int ODD = 0, EVEN = 0;
    if (dep[u] < dep[v]) {
        swap(u, v);
    }
    for (int i = LOGN; i >= 0; i--) {
        if (dep[fa[i][u]] >= dep[v]) {
            ODD = max(ODD, odd[i][u]);
            EVEN = max(EVEN, even[i][u]);
            u = fa[i][u];
        }
    }
    if (u == v) {
        return { ODD, EVEN };
    }
    for (int i = LOGN; i >= 0; i--) {
        if (fa[i][u] != fa[i][v]) {
            ODD = max({ ODD, odd[i][u], odd[i][v] });
            EVEN = max({ EVEN, even[i][u], even[i][v] });
            u = fa[i][u];
            v = fa[i][v];
        }
    }
    ODD = max(ODD, odd[0][u]);
    EVEN = max(EVEN, even[0][u]);
    return { ODD, EVEN };
}
void solve()
{
    cin >> n >> m;
    mp.clear();
    E.clear();
    init(n);
    for (int i = 0; i <= n; i++) {
        e[i].clear();
        dep[i] = 0;
    }
    for (int i = 0; i <= LOGN; i++) {
        for (int j = 0; j <= n; j++) {
            odd[i][j] = 0;
            even[i][j] = 0;
            fa[i][j] = 0;
        }
    }
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (u > v) {
            swap(u, v);
        }
        E.pb({ w, u, v });
    }
    sort(E.begin(), E.end());
    ll ans = 0;
    int cnt = 0;
    for (auto [w, u, v] : E) {
        if (join(u, v)) {
            mp[{ u, v }] = w;
            ans += w;
            e[u].pb({ v, w });
            e[v].pb({ u, w });
            cnt++;
        }
    }
    if (cnt < n - 1) {
        cout << "-1 -1" << Endl;
        return;
    }
    dfs(1, 0);
    for (int i = 1; i <= LOGN; i++) {
        for (int j = 1; j <= n; j++) {
            odd[i][j] = max(odd[i - 1][j], odd[i - 1][fa[i - 1][j]]);
            even[i][j] = max(even[i - 1][j], even[i - 1][fa[i - 1][j]]);
            fa[i][j] = fa[i - 1][fa[i - 1][j]];
        }
    }
    ll res = INF;
    for (auto [w, u, v] : E) {
        auto now = mp.find({ u, v });
        if (now != mp.end()) {
            ll ww = (*now).rs;
            if (ww == w) {
                continue;
            }
            if (((w - ww) & 1) == 0) {
                continue;
            }
            res = min(res, w - ww);
            assert(w > ww);
            continue;
        }
        auto [ODD, EVEN] = LCA(u, v);
        if ((w % 2) && EVEN != 0) {
            res = min(res, w - EVEN);
            assert(w > EVEN);
        } else if ((w % 2 == 0) && ODD != 0) {
            res = min(res, w - ODD);
            assert(w > ODD);
        }
    }
    if (res == INF) {
        res = -1;
    }
    if (ans & 1) {
        if (res == -1) {
            cout << "-1 ";
        } else {
            cout << ans + res << " ";
        }
        cout << ans << Endl;
    } else {
        cout << ans << " ";
        if (res == -1) {
            cout << "-1\n";
        } else {
            cout << ans + res << "\n";
        }

        // cout << ans << " " << (res == -1 ? res : res + ans) << Endl;
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    cin >> _;

    while (_--) {
        solve();
    }
    return 0;
}