#include<bits/stdc++.h>

using namespace std;

#define int long long
#define pb push_back
#define F first 
#define S second 

const int mol=998244353;

vector<pair<int, int>>node[200005];
int dsu[200005];
int find(int g){
    if(g==dsu[g]) return g;
    return dsu[g]=find(dsu[g]);
}
void un(int g, int h){
    g=find(g), h=find(h);
    if(g==h) return;
    dsu[g]=h;
}
int p[20][200005], q[20][200005], lcc[20][200005];
int dep[200005];
void dfs(int v, int pre){
    dep[v]=dep[pre]+1;
    lcc[0][v]=pre;
    if(v==pre) p[0][v]=1e18, q[0][v]=1e18;
    for(auto k: node[v]){
        if(k.F==pre) continue;
        q[0][k.F]=1e18, p[0][k.F]=1e18;
        if(k.S%2) p[0][k.F]=k.S;
        else q[0][k.F]=k.S;
        dfs(k.F, v);
    }
}
int lccp(int g, int h){
    if(dep[g]<dep[h]) swap(g, h);
    int t=19, ans=1e18;
    while(t>=0){
        int tt=lcc[t][g];
        if(dep[tt]>=dep[h]) ans=min(ans, p[t][g]), g=tt;
        t--;
    }
    t=19;
    if(g==h) return ans;
    while(t>=0){
        int t1=lcc[t][g], t2=lcc[t][h];
        if(t1!=t2){
            ans=min({ans, p[t][g], p[t][h]}), g=t1, h=t2;
        }
        t--;
    }
    ans=min({ans, p[0][g], p[0][h]});
    return ans;
}
int lccq(int g, int h){
    if(dep[g]<dep[h]) swap(g, h);
    int t=19, ans=1e18;
    while(t>=0){
        int tt=lcc[t][g];
        if(dep[tt]>=dep[h]) ans=min(ans, q[t][g]), g=tt;
        t--;
    }
    t=19;
    if(g==h) return ans;
    while(t>=0){
        int t1=lcc[t][g], t2=lcc[t][h];
        if(t1!=t2){
            ans=min({ans, q[t][g], q[t][h]}), g=t1, h=t2;
        }
        t--;
    }
    ans=min({ans, q[0][g], q[0][h]});
    return ans;
}


void solve(){
    int n, m;
    cin>>n>>m;
    vector<tuple<int, int, int>>mm, nn;
    for(int i=1;i<=n;i++) node[i].clear(), dsu[i]=i;
    dep[1]=0;
    for(int i=1;i<=m;i++){
        int g, h, c;
        cin>>g>>h>>c;
        mm.pb({c, g, h});
    }   
    int ans1=-1, ans2=-1, cc=0, ans=0;
    sort(mm.begin(), mm.end());

    for(auto[t1, t2, t3]: mm){
        int g=t2, h=t3;
        if(find(g)==find(h)) {nn.pb({t1, t2, t3});continue;}
        un(g, h), ans+=t1;
        cc++;
        node[t2].pb({t3, t1});
        node[t3].pb({t2, t1});
    }
    if(cc!=n-1){
        cout<<"-1 -1\n";
        return;
    }
    if(ans%2) ans1=ans;
    else ans2=ans;
    dfs(1, 1);
    for(int i=1;i<=19;i++) for(int j=1;j<=n;j++) lcc[i][j]=lcc[i-1][lcc[i-1][j]], p[i][j]=min(p[i-1][j], p[i-1][lcc[i-1][j]]), q[i][j]=min(q[i-1][j], q[i-1][lcc[i-1][j]]);
    int tot=1e18;
    for(auto [t1, t2, t3]: nn){
        int v;
        if(t1%2) {
            v=lccq(t2, t3);
            if(v==1e18) continue;
            tot=min(tot, t1-v);
        }
        else {
            v=lccp(t2, t3);
            if(v==1e18) continue;
            tot=min(tot, t1-v);
        }
    }
    if(tot!=1e18){
        if(ans2==-1) ans2=ans1+tot;
        else ans1=ans2+tot;
    }
    cout<<ans2<<" "<<ans1<<"\n";
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int t;
    cin>>t;
    while(t--)
    solve();
    return 0;
}