#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=5e5+10;
int T,n,m,E,lg[N],head[N],rt[N],dep[N],link[M*2],to[M*2],val[M*2],f[N][21],g[N][21][2];
long long ans[2];
bool vis[N];
struct edge{int u,v,w;}e[M];
void init() {
    E=0,ans[0]=ans[1]=-1,lg[1]=0;
    for(int i=1;i<=n;i++)head[i]=0,rt[i]=i,f[i][0]=g[i][0][0]=g[i][0][1]=0;
    for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
    for(int i=1;i<=m;i++)vis[i]=0;
}
int root(int x) {
    if(rt[x]==x)return x;
    return rt[x]=root(rt[x]);
}
bool cmp(edge x,edge y){return x.w<y.w;}
void add(int u,int v,int w){to[++E]=v,link[E]=head[u],head[u]=E,val[E]=w;}
int query(int u,int v,int o) {
    int res=0;
    while(dep[u]!=dep[v]) {
        if(dep[u]<dep[v])swap(u,v);
        int tmp=lg[dep[u]-dep[v]];
        res=max(res,g[u][tmp][o]),u=f[u][tmp];
    }if(u==v)return res;
    for(int i=19;i>=0;i--)if(f[u][i]!=f[v][i])
        res=max(res,max(g[u][i][o],g[v][i][o])),u=f[u][i],v=f[v][i];
    return max(res,max(g[u][0][o],g[v][0][o]));
}
void dfs(int u) {
    for(int i=1;i<20;i++)f[u][i]=f[f[u][i-1]][i-1],
        g[u][i][0]=max(g[f[u][i-1]][i-1][0],g[u][i-1][0]),
        g[u][i][1]=max(g[f[u][i-1]][i-1][1],g[u][i-1][1]);
    dep[u]=dep[f[u][0]]+1;
    for(int i=head[u];i;i=link[i]) {
        int v=to[i];
        if(v==f[u][0])continue;
        f[v][0]=u,g[v][0][val[i]&1]=val[i],dfs(v);
    }
}
int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&m);
        init();
        for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
        sort(e+1,e+m+1,cmp);
        long long res=0,tmp;
        for(int i=1;i<=m;i++) {
            int u=e[i].u,v=e[i].v,w=e[i].w,ru=root(u),rv=root(v);
            if(ru==rv)continue;
            rt[rv]=ru,add(u,v,w),add(v,u,w),vis[i]=1,res+=w;
        }ans[res&1]=res,tmp=res,res=LLONG_MAX;
        if(E/2!=n-1){printf("-1 -1\n");continue;}
        dfs(1);
        for(int i=1;i<=m;i++)if(!vis[i]) {
            int u=e[i].u,v=e[i].v,w=e[i].w,cur=query(u,v,(w&1)^1);
            if(!cur)continue;
            res=min(res,tmp+w-cur);
        }if(res==LLONG_MAX)res=-1;
        if(ans[0]>=0)ans[1]=res;
        else ans[0]=res;
        printf("%lld %lld\n",ans[0],ans[1]);
    }
}