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


#include <algorithm>
#include <cassert>
#include <vector>

namespace atcoder {

// Implement (union by size) + (path compression)
// Reference:
// Zvi Galil and Giuseppe F. Italiano,
// Data structures and algorithms for disjoint set union problems
struct dsu {
  public:
    dsu() : _n(0) {}
    dsu(int n) : _n(n), parent_or_size(n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

  private:
    int _n;
    // root node: -1 * component size
    // otherwise: parent
    std::vector<int> parent_or_size;
};

}  // namespace atcoder

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,-1));
    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[0][v]=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]=pare[t][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) {
                RE=max(RE,HE[k][u]);
                RO=max(RO,HO[k][u]);
                u = pare[k][u];
            }
        }
        if(u!=v){
             
            for (int k = K - 1; k >= 0; k--) {
                if (pare[k][u] != 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]);
                    u = pare[k][u];
                    v = pare[k][v];
                }
            }
            RE=max(RE,HE[0][v]);
            RO=max(RO,HO[0][v]);
            
            RE=max(RE,HE[0][u]);
            RO=max(RO,HO[0][u]);
        }
        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();
  
}