#include <bits/stdc++.h>
#define int long long

using namespace std;
struct DSU { 
    vector <int> f, sz;

	DSU () {}

    DSU (int n) : f (n + 1), sz (n + 1) { 
        iota (f.begin (), f.end (), 0); 
        fill (sz.begin (), sz.end (), 1);
    }

    void init (int n) {
        f.resize (n + 1);
        sz.resize (n + 1);
        iota (f.begin (), f.end (), 0);
        fill (sz.begin (), sz.end (), 1);
    }

    int find (int x) { 
        return f[x] = f[x] == x ? x : find (f[x]); 
    }

    void merge (int x, int y) { 
        int fa = find (x), fb = find (y);
        if (fa != fb) {
            sz[fb] += sz[fa];
            f[fa] = fb; 
        }
    }

    int size (int x) {
        return sz[find (x)];
    }

    bool same (int x, int y) { 
        return find (x) == find (y); 
    }
};

void solve () {
    int n, m;
    cin >> n >> m;

    vector <array <int, 3>> edge (m);
    for (auto &[x, y, z] : edge) {
        cin >> x >> y >> z;
    }

    sort (edge.begin (), edge.end (), 
        [&](const array <int, 3> &x, const array <int, 3> &y) {
            return x[2] < y[2];
        }
    );

    int sum = 0;
    int ans = 0;
    DSU dsu (n);
    vector <vector <pair <int, int>>> e (n + 1);
    for (auto [x, y, z] : edge) {
        if (! dsu.same (x, y)) {
            dsu.merge (x, y);
            ans += z;
            sum ++;
            e[x].push_back ({y, z});
            e[y].push_back ({x, z});
        }
    }

    if (sum < n - 1) {
        cout << -1 << " " << -1 << '\n';
        return;
    }

    array <int, 2> out {-1, -1};
    out[ans & 1] = ans;

    const int lg = __lg (n);

    vector <int> dep (n + 1);
    vector f (n + 1, vector <int> (lg + 1));
    vector mx (n + 1, vector (lg + 1, array <int, 2> {-1, -1}));

    auto dfs = [&] (auto &&self, int x, int fa) -> void {
        f[x][0] = fa;
        dep[x] = dep[fa] + 1;
        for (int i = 1; i <= lg; i ++) {
            f[x][i] = f[f[x][i - 1]][i - 1];
            mx[x][i][0] = max (mx[f[x][i - 1]][i - 1][0], mx[x][i - 1][0]);
            mx[x][i][1] = max (mx[f[x][i - 1]][i - 1][1], mx[x][i - 1][1]);
        }
        for (auto [y, z] : e[x]) {
            if (y == fa) {
                continue;
            }
            mx[y][0][0] = mx[y][0][1] = z;
            self (self, y, x);
        }
    };
    dfs (dfs, 1, 0);

    auto query = [&] (int x, int y, int c) {
        if (dep[x] < dep[y]) {
            swap (x, y);
        }
        int ans = -1;
        for (int i = lg; i >= 0; i --) {
            if (dep[f[x][i]] >= dep[y]) {
                ans = max (ans, mx[x][i][c]);
                x = f[x][i];
            }
        }
        if (x == y) {
            return ans;
        }
        for (int i = lg; i >= 0; i --) {
            if (f[x][i] != f[y][i]) {
                ans = max ({ans, mx[x][i][c], mx[y][i][c]});
                x = f[x][i];
                y = f[y][i];
            }
        }
        return max ({ans, mx[x][0][c], mx[y][0][c]});
    };

    for (auto [x, y, z] : edge) {
        int t = query (x, y, z & 1 ^ 1);
        if (t != -1) {
            int now = ans - t + z;
            if (out[now & 1] == -1 || out[now & 1] > now) {
                out[now & 1] = now;
            }
        }
    }
    
    cout << out[0] << " " << out[1] << '\n';
}

signed main () {
    ios::sync_with_stdio (false);
    cin.tie (nullptr);

    int T = 1;
    cin >> T;

    while (T --) {
        solve ();
    }

    return 0;
}