#include <bits/stdc++.h>

#define endl "\n"
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

struct edgds {
    int u, v, w;
};

struct DSU {
    std::vector<int> f, siz;
    DSU() {}
    DSU(int n) { init(n); }
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (siz[x] < siz[y]) {
            swap(x, y);
        }
        siz[x] += siz[y];
        f[y] = x;
        // for (auto i : s[y]) {
        //     s[x].push_back(i);
        // }
        return true;
    }
    int size(int x) { return siz[find(x)]; }
};

int n, m, fa[N][20], dep[N];
int le[2][N][20];
int Log2[N];
vector<PII> tr[N];
bool st[N];
const int M = 5e5 + 10;
bool vis[M];
void dfs(int x, int fath = 0, int w = 0) {
    if (st[x])
        return;
    st[x] = true;
    dep[x] = dep[fath] + 1;
    fa[x][0] = fath;
    if (w & 1) {
        le[1][x][0] = w;
    } else {
        le[0][x][0] = w;
    }
    for (int i = 1; i <= Log2[dep[x]]; i++) {
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
        le[0][x][i] = max(le[0][x][i - 1], le[0][fa[x][i - 1]][i - 1]);
        le[1][x][i] = max(le[1][x][i - 1], le[1][fa[x][i - 1]][i - 1]);
    }
    for (auto [y, ww] : tr[x]) {
        dfs(y, x, ww);
    }
}

PII lca(int x, int y) {
    PII res = {0, 0};
    if (dep[x] < dep[y])
        swap(x, y);
    while (dep[x] != dep[y]) {
        res.first = max(res.first, le[0][x][Log2[dep[x] - dep[y]]]);
        res.second = max(res.second, le[1][x][Log2[dep[x] - dep[y]]]);
        x = fa[x][Log2[dep[x] - dep[y]]];
    }
    if (x == y)
        return res;
    for (int j = Log2[dep[x]]; j >= 0; j--) {
        if (fa[x][j] != fa[y][j]) {
            res.first = max(res.first, max(le[0][x][j], le[0][y][j]));
            res.second = max(res.second, max(le[1][x][j], le[1][y][j]));
            x = fa[x][j], y = fa[y][j];
        }
    }
    res.first = max(res.first, max(le[0][x][0], le[0][y][0]));
    res.second = max(res.second, max(le[1][x][0], le[1][y][0]));
    return res;
}
void init(int n, int m) {
    for (int i = 0; i <= n; ++i) {
        Log2[i] = Log2[i / 2] + 1;
        tr[i].clear();
        st[i] = false;
        for (int j = 0; j < 20; j++) {
            le[0][i][j] = le[1][i][j] = 0;
            fa[i][j] = 0;
            dep[i] = 0;
        }
    }
    for (int i = 0; i < m; i++) {
        vis[i] = false;
    }
}
void solve() {
    cin >> n >> m;
    init(n, m);
    vector<edgds> e(m);
    // vector<PII> g[n + 10];
    for (int i = 0; i < m; i++) {
        cin >> e[i].u >> e[i].v >> e[i].w;
        // g[e[i].u].emplace_back(e[i].v, e[i].w);
        // g[e[i].v].emplace_back(e[i].u, e[i].w);
    }
    sort(e.begin(), e.end(), [](edgds a, edgds b) { return a.w < b.w; });
    DSU dsu(n + 10);
    LL ans = 0, minval = INF;
    int cnt = 0;
    for (int i = 0; i < m; i++) {
        auto [u, v, w] = e[i];
        if (!dsu.same(u, v)) {
            dsu.merge(u, v);
            ans += w;
            cnt++;
            vis[i] = true;
            tr[u].emplace_back(v, w);
            tr[v].emplace_back(u, w);
        }
    }
    dfs(1);
    for (int i = 0; i < m; i++) {
        if (vis[i])
            continue;
        auto [u, v, w] = e[i];
        auto [l0, l1] = lca(u, v);
        if (w & 1) {
            if (l0 != 0)
                minval = min(minval, 1LL * w - l0);
        } else {
            if (l1 != 0)
                minval = min(minval, 1LL * w - l1);
        }
    }
    LL t0 = -1, t1 = -1;
    if (cnt == n - 1) {
        if (ans & 1) {
            t1 = ans;
            if (minval != INF) {
                t0 = ans + minval;
            }
        } else {
            t0 = ans;
            if (minval != INF) {
                t1 = ans + minval;
            }
        }
    }

    cout << t0 << " " << t1 << endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}