#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define range(x) (x).begin(), (x).end()
const int dir[][2] = {1, 0, -1, 0, 0, 1, 0, -1};

const int N = 200005;
const int M = 2 * N;
int head[N], ver[M], Next[M], edge[M];
int tot;
void add(int x, int y, int z)
{
    ver[++tot] = y;
    Next[tot] = head[x];
    edge[tot] = z;
    head[x] = tot;
}

queue<int> q;
int d[N];
int f[N][20];
int mx[N][20][2];

void bfs(int x)
{
    d[x] = 1;
    q.push(x);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i; i = Next[i]) {
            int y = ver[i];
            int z = edge[i];
            if (d[y])
                continue;
            d[y] = d[u] + 1;
            q.push(y);

            f[y][0] = u;
            mx[y][0][z & 1] = z;
            mx[y][0][(z & 1) ^ 1] = 0;
            for (int k = 1; k <= 18; k++) {
                f[y][k] = f[f[y][k - 1]][k - 1];
                for (int j = 0; j < 2; ++j)
                    mx[y][k][j] = max(mx[y][k - 1][j], mx[f[y][k - 1]][k - 1][j]);
            }
        }
    }
    return;
}

int ask(int x, int y, bool flag)
{
    if (d[x] < d[y])
        swap(x, y);

    int ans = 0;
    for (int k = 18; k >= 0; k--)
        if (d[f[x][k]] >= d[y]) {
            ans = max(ans, mx[x][k][flag]);
            x = f[x][k];
        }

    if (x == y)
        return ans;

    for (int k = 18; k >= 0; k--)
        if (f[x][k] != f[y][k]) {
            ans = max(ans, mx[x][k][flag]);
            ans = max(ans, mx[y][k][flag]);
            x = f[x][k], y = f[y][k];
        }

    return max(ans, max(mx[x][0][flag], mx[y][0][flag]));
}

int fa[N];
int get(int x)
{
    if (x == fa[x])
        return x;
    return fa[x] = get(fa[x]);
}

void merge(int x, int y)
{
    int a = get(x);
    int b = get(y);
    if (a == b)
        return;
    fa[b] = a;
    return;
}

void init(int n)
{
    for (int i = 1; i <= n; ++i) {
        head[i] = 0;
        fa[i] = i;
        for (int k = 0; k <= 18; ++k) {
            f[i][k] = 0;
            mx[i][k][0] = mx[i][k][1] = 0;
        }
    }
    tot = 0;
}

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

    ll sum = 0;
    vector<pair<int, pii>> e;
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        e.push_back({w, {u, v}});
    }

    sort(range(e));
    vector<pair<int, pii>> del;
    for (const auto &[ds, eg] : e) {
        auto [x, y] = eg;
        if (get(x) == get(y)) {
            del.push_back({ds, eg});
            continue;
        }
        sum += ds;
        merge(x, y);
        add(x, y, ds);
        add(y, x, ds);
    }

    int ck = 0;
    for (int i = 1; i <= n; ++i)
        ck += (i == get(i));
    if (ck > 1) {
        cout << "-1 -1\n";
        return;
    }

    bfs(1);

    ll ans[2] = {0, 0};
    ans[sum & 1] = sum;
    ans[(sum & 1) ^ 1] = LLONG_MAX;
    for (const auto &[w, eg] : del) {
        auto [u, v] = eg;

        int mx = ask(u, v, (w & 1) ^ 1);
        if (mx)
            ans[(sum & 1) ^ 1] = min(ans[(sum & 1) ^ 1], w - mx + sum);
    }
    // cout << ask(2, 4, 1) << '\n';
    for (int i = 0; i < 2; ++i)
        cout << (ans[i] == LLONG_MAX ? -1 : ans[i]) << ' ';
    cout << '\n';
}

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

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