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

using ui = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(l);i>=(r);--i)
#define repn(i,n)  for(int i=0;i<(n);++i)
#define sizc(x) ((int)x.size())
#define allc(x) x.begin(),x.end()
#define fir first
#define sec second

constexpr int N = 2e5+5, M = 5e5+5;
constexpr ll inf = 1e18;

int n,m;
struct qwq{
    int u,v;ll w;
    bool operator<(const qwq &o)const{return w<o.w;}
}e[M];

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

bool ot[M];
vector<pair<int,ll>> G[N];

int d[N],to[20][N];
ll mw[2][20][N];

void dfs(int u,int fa){
    d[u]=d[fa]+1,to[0][u]=fa;
    for(auto p:G[u]){
        int v=p.fir;ll w=p.sec;
        if(v==fa)continue;
        mw[w&1][0][v]=w,mw[(w&1)^1][0][v]=-inf;
        dfs(v,u);
    }
}

void solve(){
    cin>>n>>m;
    rep(i,1,m)cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e+1,e+m+1);
    rep(i,1,m)ot[i]=0;
    ll mst=0;
    rep(i,1,n)G[i].clear();
    rep(i,1,n)fa[i]=i;
    rep(i,1,m){
        int u=find(e[i].u),v=find(e[i].v);
        if(u!=v){
            ot[i]=1;
            mst+=e[i].w;
            fa[v]=u;
            G[e[i].u].emplace_back(e[i].v,e[i].w);
            G[e[i].u].emplace_back(e[i].u,e[i].w);
        }
    }
    if(count(ot+1,ot+m+1,1)!=n-1){cout<<"-1 -1\n";return;}
    ll mino=inf;
    dfs(1,0);
    rep(j,1,19)rep(i,1,n){
        to[j][i]=to[j-1][to[j-1][i]];
        repn(t,2)mw[t][j][i]=max(mw[t][j-1][i],mw[t][j-1][to[j-1][i]]);
    }
    rep(i,1,m)if(!ot[i]){
        int u=e[i].u,v=e[i].v,w=e[i].w;
        if(d[u]<d[v])swap(u,v);
        ll mx=-inf;
        per(j,19,0)if(d[to[j][u]]>=d[v]){
            mx=max(mx,mw[(w&1)^1][j][u]);
            u=to[j][u];
        }
        if(u!=v){
            per(j,19,0)if(to[j][u]!=to[j][v]){
                mx=max(mx,mw[(w&1)^1][j][u]);
                u=to[j][u];
                mx=max(mx,mw[(w&1)^1][j][v]);
                v=to[j][v];
            }
            mx=max(mx,mw[(w&1)^1][0][u]);
            mx=max(mx,mw[(w&1)^1][0][v]);
        }
        mino=min(mino,mst-mx+e[i].w);
    }
    if(mst&1)swap(mst,mino);
    cout<<(mst==inf?-1:mst)<<' '<<(mino==inf?-1:mino)<<'\n';
}

signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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