#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define FOR() ll le=e[u].size();for(ll i=0;i<le;i++)
#define QWQ cout<<"QwQ\n";
#define ll long long
#include <vector>
#include <queue>
#include <map>

using namespace std;
const ll N=501010;
const ll qwq=303030;
const ll inf=0x3f3f3f3f3f3f3f3f;

inline ll read() {
    ll sum = 0, ff = 1; char c = getchar();
    while(c<'0' || c>'9') { if(c=='-') ff = -1; c = getchar(); }
    while(c>='0'&&c<='9') { sum = sum * 10 + c - '0'; c = getchar(); }
    return sum * ff;
}

ll T;
ll n,m;
struct E{
    ll x,y,we;
}e[N];
bool shu[N];
inline bool cmp(E A,E B) { return A.we < B.we; }
struct D{
    ll to,we;
};
vector <D> d[N];
ll f[N][22],mi[2][N][22];
ll fa[N],dep[N];

ll find(ll x) { return fa[x]==x ? x : fa[x]=find(fa[x]); }

void chushihua() {
    for(ll i=1;i<=n;i++) d[i].clear();
    for(ll i=1;i<=m;i++) shu[i] = 0;
}

void DFS(ll u,ll ff) {
    dep[u] = dep[ff] + 1;
    f[u][0] = ff;
    for(D vv : d[u]) {
        ll v = vv.to, w = vv.we;
        if(v==ff) continue;
        mi[w&1][v][0] = w;
        DFS(v,u);
    }
}

inline ll ask(ll x,ll y,ll cl) {
    ll res = inf;
    if(dep[x]<dep[y]) swap(x,y);
    for(ll k=20;k>=0;k--) {
        if(dep[f[x][k]]>=dep[y]) res = min(res,mi[cl][x][k]), x = f[x][k];
    }
    if(x==y) return res;
    for(ll k=20;k>=0;k--) {
        if(f[x][k]!=f[y][k]) res = min(res,mi[cl][x][k]), res = min(res,mi[cl][y][k]), x = f[x][k], y = f[y][k];
    }
    res = min(res,mi[cl][x][0]);
    res = min(res,mi[cl][y][0]);
    return res;
}

int main() {
    T = read();
    while(T--) {
        chushihua();
        n = read(); m = read();
        for(ll i=1;i<=n;i++) fa[i] = i;
        for(ll i=1;i<=m;i++) {
            e[i] = { read(), read(), read() };
        }
        sort(e+1,e+m+1,cmp);
        ll ans1 = 0, ans2 = -1, cnt = 0;
        for(ll i=1;i<=m;i++) {
            ll xx = find(e[i].x);
            ll yy = find(e[i].y);
            if(xx==yy) continue;
            cnt++;
            fa[xx] = yy;
            d[e[i].x].push_back({e[i].y,e[i].we});
            d[e[i].y].push_back({e[i].x,e[i].we});
            shu[i] = 1;
            ans1 += e[i].we;
        }
        if(cnt!=n-1) {
            cout<<"-1 -1\n";
            continue;
        }
        for(ll i=1;i<=n;i++) mi[0][i][0] = mi[1][i][0] = inf;
        DFS(1,0);
        for(ll k=1;k<=20;k++)
            for(ll i=1;i<=n;i++) {
                ll ta = f[i][k-1];
                f[i][k] = f[ta][k-1];
                mi[0][i][k] = min(mi[0][i][k-1], mi[0][ta][k-1]);
                mi[1][i][k] = min(mi[1][i][k-1], mi[1][ta][k-1]);
            }

        ll xiao = inf;
        for(ll i=1;i<=m;i++) {
            if(shu[i]) continue;
            ll xin = ask(e[i].x,e[i].y,(e[i].we&1)^1);
            if(xin==inf) continue;
            xiao = min(xiao,e[i].we-xin);
        }
        if(xiao!=inf) ans2 = ans1 + xiao;
        if(ans1>0 && ans1%2==1) swap(ans1,ans2);
        if(ans2>0 && ans2%2==0) swap(ans1,ans2);
        cout<<ans1<<" "<<ans2<<"\n";
    }
    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

*/