#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#include<atcoder/dsu>
using namespace atcoder;

void solve(){
    ll N,M;
    cin>>N>>M;
    
    vector<pair<ll,pair<ll,ll>>> E(M);
    for(int i=0;i<M;i++){
        ll u,v,w;
        cin>>u>>v>>w;
        u--;v--;
        E[i]={w,{u,v}};
    }
    sort(E.begin(),E.end());
    vector<vector<pair<ll,ll>>> G(N);
    dsu d(N);
    ll an=0;
    vector<pair<ll,pair<ll,ll>>> NotE;
    for(int i=0;i<M;i++){
        ll w=E[i].first;
        auto [u,v]=E[i].second;
        if(!d.same(u,v)){
            an+=w;
            d.merge(u,v);
            G[u].push_back({v,w});
            G[v].push_back({u,w});
        }
        else{
            NotE.push_back(E[i]);
        }
    }

    if(d.size(0)!=N){
        cout<<-1<<" "<<-1<<endl;
        return;
    }

    queue<int> Q;
    vector<vector<ll>> pare(25,vector<ll>(N,-1e18));
    auto HO=pare;
    auto HE=pare;
    vector<int> dist(N,0);
    Q.push(0);
    vector<bool> seen(N,false);
    while(!Q.empty()){
        int p=Q.front();
        Q.pop();
        if(seen[p]);
        seen[p]=1;
        for(auto [v,w]:G[p]){
            if(seen[v])continue;
            Q.push(v);
            dist[v]=dist[p]+1;
            pare[v][0]=p;
            (w%2?HO:HE)[0][v]=w;
        }
    }
    
    for(int t=0;t<24;t++){
        for(int n=0;n<N;n++){
            ll p=pare[t][n];
            if(p<0){
                pare[t+1][n]=-1;
                HE[t+1][n]=HE[t][n];
                HO[t+1][n]=HO[t][n];
            }
            else{
                pare[t+1][n]=p;
                HE[t+1][n]=max(HE[t][n],HE[t][p]);
                HO[t+1][n]=max(HO[t][n],HO[t][p]);
            }
        }
    }
    ll bn=3e18;

    M=NotE.size();
    for(int i=0;i<M;i++){
        ll w=NotE[i].first;
        auto [u,v]=NotE[i].second;

        if(dist[u]<dist[v])swap(u,v);
        int K=pare.size();
        ll RO=-1e18,RE=-1e18;;
        for (int k = 0; k < K; k++) {
            if ((dist[u] - dist[v]) >> k & 1) {
                u = pare[k][u];
                RE=max(RE,HE[k][u]);
                RO=max(RO,HO[k][u]);
            }
        }
        if(u!=v){
            for (int k = K - 1; k >= 0; k--) {
                if (pare[k][u] != pare[k][v]) {
                    u = pare[k][u];
                    v = pare[k][v];

                    RE=max(RE,HE[k][u]);
                    RO=max(RO,HO[k][u]);

                    RE=max(RE,HE[k][v]);
                    RO=max(RO,HO[k][v]);
                }
            }
            RE=max(RE,HE[0][v]);
            RO=max(RO,HO[0][v]);
        }
        if(w%2){
            bn=min(bn,an+w-RE);
        }
        else{
            bn=min(bn,an+w-RO);
        }
    }
    if(an%2){
        if(bn>1e17)cout<<-1<<" ";
        else cout<<bn<<" ";
        cout<<an<<"\n";
    }
    else{
        cout<<an<<" ";
        if(bn>1e17)cout<<-1<<"\n";
        else cout<<bn<<"\n";
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin>>T;
    while(T--)solve();
  
}

answer.code:5:9: fatal error: atcoder/dsu: No such file or directory
    5 | #include<atcoder/dsu>
      |         ^~~~~~~~~~~~~
compilation terminated.