#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define gcd __gcd
using namespace std;
int uni[200005];
int _find(int x){
    if (x == uni[x]) return x;
    return uni[x] = _find(uni[x]);
}
void join(int x, int y){
    uni[_find(x)] = _find(y);
}
vector<pair<int, int> > g[200005];
int fa[200005][25];
int maxOdd[200005][25];
int maxEven[200005][25];
int dep[200005];
void dfs(int u, int ffa){
    for (int i = 1; dep[u] - (1ll << i) >= 0; i++){
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
        maxOdd[u][i] = max(maxOdd[u][i - 1], maxOdd[fa[u][i - 1]][i - 1]);
        maxEven[u][i] = max(maxEven[u][i - 1], maxEven[fa[u][i - 1]][i - 1]);
    }
    for (auto [v, w] : g[u]){
        if (v == ffa) continue;
        fa[v][0] = u;
        if (w & 1ll){
            maxOdd[v][0] = w;
            maxEven[v][0] = 0;
        }
        else {
            maxEven[v][0] = w;
            maxOdd[v][0] = 0;
        }
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
}
int lca(int u, int v){
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = 20; i >= 0; i--){
        if (dep[fa[u][i]] >= dep[v]){
            u = fa[u][i];
        }
        if (u == v) return u;
    }
    for (int i = 20; i >= 0; i--){
        if (fa[u][i] != fa[v][i]){
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}
int getMaxOdd(int u, int v){
    int f = lca(u, v);
    int maxn = 0;
    int d = dep[u] - dep[f];
    int p = u;
    for (int bit = 20; bit >= 0; bit--){
        if (d >> bit & 1){
            maxn = max(maxn, maxOdd[p][bit]);
            p = fa[p][bit];
        }
    }
    d = dep[v] - dep[f];
    p = v;
    for (int bit = 20; bit >= 0; bit--){
        if (d >> bit & 1){
            maxn = max(maxn, maxOdd[p][bit]);
            p = fa[p][bit];
        }
    }
    return maxn;
}
int getMaxEven(int u, int v){
    int f = lca(u, v);
    int maxn = 0;
    int d = dep[u] - dep[f];
    int p = u;
    for (int bit = 20; bit >= 0; bit--){
        if (d >> bit & 1){
            maxn = max(maxn, maxEven[p][bit]);
            p = fa[p][bit];
        }
    }
    d = dep[v] - dep[f];
    p = v;
    for (int bit = 20; bit >= 0; bit--){
        if (d >> bit & 1){
            maxn = max(maxn, maxEven[p][bit]);
            p = fa[p][bit];
        }
    }
    return maxn;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--){
        int n, m;
        cin >> n >> m;
        vector< array<int, 3> > e(m + 5);
        vector<int> vis(m + 5);
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j < 3; j++){
                cin >> e[i][j];
            }
        }
        sort(e.begin() + 1, e.begin() + m + 1, [&](array<int, 3> x, array<int, 3> y){
            return x[2] < y[2];
        });
        int cnt = 0;
        for (int i = 1; i <= n; i++){
            uni[i] = i;
            g[i].clear();
        }
        int sum = 0;
        for (int i = 1; i <= m; i++){
            int u = e[i][0], v = e[i][1], w = e[i][2];
            if (_find(u) == _find(v)) continue;
            vis[i] = 1;
            join(u, v);
            cnt++;
            g[u].push_back({v, w});
            g[v].push_back({u, w});
            sum += w;
        }
        if (cnt != n - 1) {
            cout << -1 << ' ' << -1 << endl;
            continue;
        }
        dep[1] = 1;
        dfs(1, 1);
        int odd = LLONG_MAX, even = LLONG_MAX;
        int flag = 0;
        if (sum & 1ll) odd = sum;
        else even = sum, flag++;
        for (int i = 1; i <= m; i++){
            if (vis[i]) continue;
            int u = e[i][0], v = e[i][1], w = e[i][2];
            if (w & 1ll){
                int res = getMaxEven(u, v);
                if (!res) continue;
                int anw = sum - res + w;
                odd = min(odd, sum - res + w);
                even = min(even, sum - res + w);
            }
            else {
                int res = getMaxOdd(u, v);
                if (!res) continue;
                int anw = sum - res + w;
                odd = min(odd, sum - res + w);
                even = min(even, sum - res + w);
            }
        }
        if (even == LLONG_MAX) even = -1;
        if (odd == LLONG_MAX) odd = -1;
        cout << even << ' ' << odd << endl;
    }
    return 0;
}