#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 500005;
struct Ordered
{
    tuple<int, int, int> black[MAXN], white[MAXN];
    int i = 0, j = 0, n = 0, m = 0, d = 0;
    void init(int _n, int _m)
    {
        n = _n, m = _m;
        sort(black, black + n);
        sort(white, white + m);
    }
    bool empty()
    {
        return i == n && j == m;
    }
    tuple<int, int, int> getNext()
    {
        if (j >= m || i < n && get<0>(black[i]) + d < get<0>(white[j]))
            return black[i++];
        else
            return white[j++];
    }
} o;
int fa[MAXN];
int root(int x)
{
    return fa[x] == x ? x : (fa[x] = root(fa[x]));
}
bool merge(int x, int y)
{
    x = root(x), y = root(y);
    return x != y && (fa[x] = y, 1);
}
int N;
pair<int, int> work(int delta)
{
    o.i = o.j = 0;
    o.d = delta;
    int x = 0, y = 0, xn = 0;
    for (int i = 1; i <= N; i++)
        fa[i] = i;
    while (!o.empty())
    {
        int w, u, v;
        tie(w, u, v) = o.getNext();
        if(N == 16) cout << w << " " << u << " " << v << " " << root(u) << " " << root(v) << endl;
        if (merge(u, v))
        {
            y += w;
            xn++;
            if (w & 1)
                y += delta, x++;
        }
    }
    if (xn < N - 1)
        return {x, 1e9};
    return {x, y};
}
int getAns(int k)
{
    int l = -1e9, r = 1e9, ans = 1e9;
    while (r > l)
    {
        int m = (l + r) >> 1;
        int x, y;
        tie(x, y) = work(m);
        // cout << l << " " << m << " " << r << " " << x << " " << y << endl;
        if (x > k)
            l = m + 1;
        else if (x <= k)
            r = m, ans = y - m * x;
    }
    return r == -1e9 ? 1e9 : ans;
}
signed main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n, m;
        cin >> n >> m;
        N = n;
        int b = 0, w = 0;
        for (int i = 0; i < m; i++)
        {
            int u, v, W;
            cin >> u >> v >> W;
            if (W & 1)
                o.black[b++] = {W, u, v};
            else
                o.white[w++] = {W, u, v};
        }
        o.init(b, w);
        int x0, y0;
        tie(x0, y0) = work(0);
        int y1 = min(getAns(x0 - 1), getAns(x0 + 1));
        if (y0 >= 1e9)
            y0 = -1;
        if (y1 >= 1e9)
            y1 = -1;
        if (x0 & 1)
            cout << y1 << " " << y0 << endl;
        else
            cout << y0 << " " << y1 << endl;
        // cout << getAns(x0 + 1) << endl;
        // cout << x0 << " " << y0 << " " << getAns(x0 - 1) << " " << getAns(x0 + 1) << endl;
        // int y1 = max(x0 && x0 - 1 + w >= n - 1 ? getAns(x0 - 1) : -1e9, x0 + 1 <= b && x0 + 1 <= n - 1 ? getAns(x0 + 1) : -1e9);
    }
    return 0;
}