#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fore(i, l, r) for (ll i = (int)l; i <= (int)r; i++)
#define ford(i, r, l) for (ll i = (int)r; i >= (int)l; i--)
const int MAXN = 2123456LL;
ll T, n, m, a[MAXN], zu[MAXN];
ll tot, hand[MAXN], nxt[MAXN], to[MAXN], val[MAXN], dep[MAXN];
ll fa[MAXN][31], qi[MAXN][31], ou[MAXN][31];
struct node
{
    ll l, r, w;
} ken[MAXN];
void add(ll x, ll y, ll w)
{
    tot++;
    to[tot] = y;
    nxt[tot] = hand[x];
    val[tot] = w;
    hand[x] = tot;
}
bool cmp(node x, node y)
{
    return x.w < y.w;
}
ll getzu(ll x)
{
    if (x == zu[x])
        return x;
    return zu[x] = getzu(zu[x]);
}
void merge(ll x, ll y)
{
    zu[getzu(y)] = zu[getzu(x)];
}
ll sum1 = 0, ans1, ans2;
void sou(ll t)
{
    fore(i, 1, 30)
    {
        fa[t][i] = fa[fa[t][i - 1]][i - 1];
        qi[t][i] = max(qi[t][i - 1], qi[fa[t][i - 1]][i - 1]);
        ou[t][i] = max(ou[t][i - 1], ou[fa[t][i - 1]][i - 1]);
    }
    sum1++;
    for (int i = hand[t]; i; i = nxt[i])
    {
        if (to[i] != 1 && fa[to[i]][0] == 0)
        {
            dep[to[i]] = dep[t] + 1;
            ans1 += val[i];
            fa[to[i]][0] = t;
            if (val[i] % 2 == 1)
            {
                qi[to[i]][0] = val[i];
                ou[to[i]][0] = 0;
            }
            else
            {
                qi[to[i]][0] = 0;
                ou[to[i]][0] = val[i];
            }
            sou(to[i]);
        }
    }
}
bool vis[MAXN];
ll lca1(ll x, ll y, ll w)
{
    if (dep[x] < dep[y])
        swap(x, y);
    ll retou = 0;
    ford(i, 30, 0)
    {
        if (dep[fa[x][i]] > dep[y])
            retou = max(retou, ou[x][i]), x = fa[x][i];
    }
    fore(i, 0, 30)
    {
        if (dep[fa[x][i]] == dep[y])
        {
            retou = max(retou, ou[x][i]), x = fa[x][i];
            break;
        }
    }

    if (x == y)
    {
        if (retou == 0)
            return 999999999999ll;
        return ans1 - retou + w;
    }
    ford(i, 30, 0)
    {
        if (fa[x][i] != fa[y][i])
        {
            retou = max(retou, ou[x][i]), x = fa[x][i];
            retou = max(retou, ou[y][i]), y = fa[y][i];
        }
    }
    fore(i, 0, 30)
    {
        if (fa[x][i] == fa[y][i])
        {
            retou = max(retou, ou[x][i]), x = fa[x][i];
            retou = max(retou, ou[y][i]), y = fa[y][i];
            if (retou == 0)
                return 999999999999ll;
            return ans1 - retou + w;
        }
    }
}
ll lca2(ll x, ll y, ll w)
{
    // cout << x << "    " << y << "   " << qi[x][10] << endl;
    if (dep[x] < dep[y])
        swap(x, y);
    ll retqi = 0;
    ford(i, 30, 0)
    {
        if (dep[fa[x][i]] > dep[y])
            retqi = max(retqi, qi[x][i]), x = fa[x][i];
    }
    fore(i, 0, 30)
    {
        if (dep[fa[x][i]] == dep[y])
        {
            retqi = max(retqi, qi[x][i]), x = fa[x][i];
            break;
        }
    }
    if (x == y)
    {
        if (retqi == 0)
            return 999999999999ll;
        return ans1 - retqi + w;
    }
    ford(i, 30, 0)
    {
        if (fa[x][i] != fa[y][i])
        {
            retqi = max(retqi, qi[x][i]), x = fa[x][i];
            retqi = max(retqi, qi[y][i]), y = fa[y][i];
        }
    }
    fore(i, 0, 30)
    {
        if (fa[x][i] == fa[y][i])
        {
            retqi = max(retqi, qi[x][i]), x = fa[x][i];
            retqi = max(retqi, qi[y][i]), y = fa[y][i];
            if (retqi == 0)
                return 999999999999ll;
            return ans1 - retqi + w;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        fore(i, 1, n)
        {
            zu[i] = i;
            fa[i][0] = 0;
            fore(j, 0, 30) qi[i][j] = 0, ou[i][j] = 0;
        }

        fore(i, 1, m)
        {
            cin >> ken[i].l >> ken[i].r >> ken[i].w;
        }
        sort(ken + 1, ken + 1 + m, cmp);
        tot = 0;
        fore(i, 1, n) hand[i] = 0;
        fore(i, 1, m)
        {
            vis[i] = 0;
            if (getzu(ken[i].l) != getzu(ken[i].r))
            {
                merge(ken[i].l, ken[i].r);
                add(ken[i].l, ken[i].r, ken[i].w);
                add(ken[i].r, ken[i].l, ken[i].w);
                vis[i] = 1;
            }
        }
        sum1 = 0;
        ans1 = 0;
        sou(1);
        if (sum1 != n)
        {
            cout << -1 << " " << -1 << endl;
            continue;
        }
        if (ans1 % 2 == 1)
        {
            ans2 = 999999999999ll;
            fore(i, 1, m)
            {
                if (!vis[i])
                {
                    if (ken[i].w % 2 == 1)
                    {
                        ans2 = min(lca1(ken[i].l, ken[i].r, ken[i].w), ans2);
                    }
                    else
                    {
                        ans2 = min(lca2(ken[i].l, ken[i].r, ken[i].w), ans2);
                    }
                }
            }
            if (ans2 == 999999999999ll)
            {
                cout << -1 << " " << ans1 << endl;
            }
            else
            {
                cout << ans2 << " " << ans1 << endl;
            }
        }
        else
        {
            ans2 = 999999999999ll;
            fore(i, 1, m)
            {
                if (!vis[i])
                {
                    if (ken[i].w % 2 == 1)
                    {
                        ans2 = min(lca1(ken[i].l, ken[i].r, ken[i].w), ans2);
                    }
                    else
                    {
                        ans2 = min(lca2(ken[i].l, ken[i].r, ken[i].w), ans2);
                    }
                }
            }
            if (ans2 == 999999999999ll)
            {
                cout << ans1 << " " << -1 << endl;
            }
            else
            {
                cout << ans1 << " " << ans2 << endl;
            }
        }
    }
    return 0;
}
/*
3
2 1
1 2 5
3 1
1 3 1
4 4
1 2 1
1 3 1
1 4 1
2 4 2

1
4 4
1 2 1
1 3 1
1 4 1
2 4 2
*/