#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int, int>
void solve();

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--)solve();
    return 0;
}
#define debug(x) cout << (#x) << " == " << (x) << '\n'
#define pii pair<int, int>
#define ft first
#define sd second
const int N = 2e5 + 10;
const int inf = 1e18;
using a3 = array<int, 3>;
vector<a3> g(N);

vector<vector<int>> v(N);
vector<int> w(N);
int get(int a, int b)
{
    return ((a << 32) | (b));
}
unordered_map<int, int> mp;
vector<int> p(N);
vector<int> vis(N);
int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}
int n, m;

void dfs_edge(int fa, int u)
{
    w[u] = mp[get(fa, u)];
    for(int& to : v[u])
    {
        if(to == fa)continue;
        else dfs_edge(u, to);
    }
}

vector<int> dep(N), sz(N), top(N), fa(N), son(N), id(N), nw(N);
int cnt;
struct node
{
    int l, r;
    array<int, 2> a;
}tr[N << 2];

void dfs1(int u, int father, int de)
{
    dep[u] = de, fa[u] = father, sz[u] = 1;
    for(int& i : v[u])
    {
        if(i == father)continue;
        dfs1(i, u, de+ 1);
        sz[u] += sz[i];
        if(sz[son[u]] < sz[i])sz[u] = i;
    }
}
void dfs2(int u, int t)
{
    id[u] = ++cnt, nw[cnt] = w[u], top[u] = t;
    if(!son[u])return;
    dfs2(son[u], t);
    for(int& j : v[u])
    {
        if(j == fa[u] || j == son[u])continue;
        else dfs2(j, j);
    }
}

void pushup(int u)
{
    //tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    //tr[u].mi = min(tr[u << 1].mi, tr[u << 1 | 1].mi);
   // tr[u].ma = max(tr[u << 1].ma, tr[u << 1 | 1].ma);
   for(int i = 0; i < 2; i++)
       tr[u].a[i] = max(tr[u << 1].a[i], tr[u << 1 | 1].a[i]);
}

void build(int u, int l, int r)
{
    //tr[u] = {l, r, nw[r], nw[r]};
    int op = nw[r] & 1;
    tr[u] = { l ,r , -inf, -inf };
    tr[u].a[op] = nw[r];
    if(l == r)return;
    else
    {
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

int query(int u, int l, int r, int op)
{
    if(tr[u].l >= l && tr[u].r <= r)return tr[u].a[op];
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        int t = -1;
        if(l <= mid)t = query(u << 1, l, r, op);
        if(r > mid)t = max(t, query(u << 1 | 1, l, r, op));
        return t;
    }
}
int query_path(int u, int v, int op)
{
    int res = 0;
    while(top[u] != top[v])
    {
        if(dep[top[u]] < dep[top[v]])swap(u, v);
        res = max(res, query(1, id[top[u]], id[u], op));
        u = fa[top[u]];
    }
    if(dep[u] < dep[v])swap(u, v);
    res = max(res, query(1, id[v], id[u], op));
    return res;
}
void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)v[i].clear();
    for(int i = 1; i <= n; i++)w[i] = 0;
    mp.clear();
    for(int i = 1; i <= n; i++)vis[i] = 0;
    for(int i = 1; i <= n; i++)dep[i] = 0;
    for(int i = 1; i <= n; i++)sz[i] = 0;
    for(int i = 1; i <= n; i++)top[i] = 0;
    for(int i = 1; i <= n; i++)fa[i] = 0;
    for(int i = 1; i <= n; i++)son[i] = 0;
    for(int i = 1; i <= n; i++)id[i] = 0;
    for(int i = 1; i <= n; i++)nw[i] = 0;
    cnt = 0;
    for(int i = 1; i <= n; i++)p[i] = i;
    for(int i = 0; i < m; i++)
    {
        cin >> g[i + 1][1] >> g[i+ 1][2] >> g[i + 1][0];
    }
    sort(g.begin() + 1, g.begin() + m + 1);

    array<int, 2> res = {inf, inf};
    int sum = 0;
    for(int i = 1; i <= m; i++)
    {
        int a = g[i][1], b = g[i][2];
        int c = g[i][0];

        a = find(a), b = find(b);
        if(a == b)continue;
        else
        {
            vis[i] = 1;
            p[a] = b;
            sum += c;
           // mp[get(a, b)] = c;
        }
    }

    if(count(vis.begin() + 1, vis.begin() + m + 1, 1) == n - 1);
    else
    {
        cout << -1 << ' ' << -1 << endl;
        return;
    }

    res[sum & 1] = sum;
    int tar = (sum & 1) ^ 1;
    for(int i = 1; i <= m; i++)
    {
        int a = g[i][1] ,b = g[i][2];
        mp[get(a, b)] = g[i][0];
        mp[get(b, a)] = g[i][0];

        if(vis[i]){
            v[a].push_back(b);
            v[b].push_back(a);
        }
    }


    dfs_edge(0, 1);
    dfs1(1, 0, 1);
    dfs2(1, 1);

    n = cnt;

    build(1, 1, n);
    for(int i = 1; i <= m; i++)
    {
        if(vis[i] == 0) {
            //debug(g[i][1]);
            //debug(g[i][2]);
           int op = g[i][0];
            op &= 1;
            op ^= 1;
            int s = sum;
            s += g[i][0];
            //debug(op);
            s -= query_path(g[i][1], g[i][2], op);
            //debug(query_path(g[i][1], g[i][2], op));
            if((s & 1) == (tar))res[tar] = min(res[tar], s);
        }
    }
    assert(w[1] == 0);
    for(int i = 0; i < 2; i++)
        if(res[i] >= inf)cout << -1 << ' ';
    else cout << res[i] << ' ';
    cout << endl;
}