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

const int N=200050;
const int M=500050;
bool inMst[M];
vector<array<int,3>> E[N];

const int H=4*N;
const int inf=1e9+7;
int ls[H],rs[H],tsz,root[2],mx[H];
void Build(int&c,int ss,int se){
    c=++tsz;
    mx[c]=-inf;
    if(ss==se)return;
    int mid=ss+se>>1;
    Build(ls[c],ss,mid);
    Build(rs[c],mid+1,se);
}
void Set(int c,int ss,int se,int qi,int x){
    if(ss==se){
        mx[c]=x;
        return;
    }
    int mid=ss+se>>1;
    if(qi<=mid)Set(ls[c],ss,mid,qi,x);
    else Set(rs[c],mid+1,se,qi,x);
    mx[c]=max(mx[ls[c]],mx[rs[c]]);
}
int Get(int c,int ss,int se,int qs,int qe){
    if(qs>qe||ss>qe||qs>se)return -inf;
    if(qs<=ss&&qe>=se)return mx[c];
    int mid=ss+se>>1;
    return max(Get(ls[c],ss,mid,qs,qe),Get(rs[c],mid+1,se,qs,qe));
}

int n,dep[N];
int bestAdd;
void DFS(int u,int p,int w){
    dep[u]=dep[p]+1;
    Set(root[w%2],1,n,dep[u],w);
    for(auto e:E[u]){
        int v=e[0],nw=e[2];
        if(inMst[e[1]]){
            if(v==p)continue;
            DFS(v,u,nw);
        }else{
            if(dep[v]<dep[u]){
                int mne=Get(root[(nw%2)^1],1,n,dep[v]+1,dep[u]);
                bestAdd=min(bestAdd,nw-mne);
            }
        }
    }
    Set(root[w%2],1,n,dep[u],-inf);
}

struct DSU{
    int p[N];
    void Init(int n){
        for(int i=1;i<=n;i++)p[i]=i;
    }
    int Find(int x){return p[x]==x?x:p[x]=Find(p[x]);}
    void Union(int x,int y){p[Find(x)]=Find(y);}
}dsu;
int main(){
    int t;
    scanf("%i",&t);
    while(t--){
        int m;
        scanf("%i %i",&n,&m);
        ll mst=0;
        vector<array<int,4>> edges;
        for(int i=1;i<=m;i++){
            int u,v,w;
            scanf("%i %i %i",&u,&v,&w);
            E[u].pb({v,i,w});
            E[v].pb({u,i,w});
            edges.pb({w,i,u,v});
            inMst[i]=false;
        }
        sort(edges.begin(),edges.end());
        dsu.Init(n);
        int cnt=0;
        for(auto e:edges){
            int u=e[2];
            int v=e[3];
            if(dsu.Find(u)!=dsu.Find(v)){
                mst+=e[0];
                inMst[e[1]]=true;
                cnt++;
                dsu.Union(u,v);
            }
        }
        if(cnt!=n-1){
            printf("-1 -1\n");
        }else{
            bestAdd=inf;
            Build(root[0],1,n);
            Build(root[1],1,n);
            DFS(1,0,0);
            ll other=bestAdd==inf?-1:mst+bestAdd;
            if(mst%2==0){
                printf("%lld %lld\n",mst,other);
            }else{
                printf("%lld %lld\n",other,mst);
            }
        }

        for(int i=1;i<=n;i++){
            E[i].clear();
        }
        for(int i=1;i<=tsz;i++){
            ls[i]=rs[i]=0;
            mx[i]=-inf;
        }
        tsz=0;
        root[0]=root[1]=0;
    }
    return 0;
}