#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pb push_back
#define ll long long
#define pii pair<int,int>

#define fi first
#define se second
#define bg begin
#define gc getchar
inline int read(){
	char ch=gc();
	int res=0;bool f=1;
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
	return f?res:-res;
}
template<typename tp>inline void chemx(tp &a,tp b){(a<b)?(a=b):0;}
template<typename tp>inline void chemn(tp &a,tp b){(a>b)?(a=b):0;}


cs int N=500005;
int fa[N][20],up1[N][20],up2[N][20];
int n,m;
cs ll inf=1e18;
cs int inf2=1e9+10;
vector<pii> e[N];
struct edge{
    int u,v,w;
}E1[N],E2[N];
int cnt,ff[N],dep[N];
int query1(int u,int v){
    int mn=inf2;
    if(dep[u]<dep[v])swap(u,v);
    for(int i=19;~i;i--)if(dep[fa[u][i]]>=dep[v]){
        mn=min(mn,up1[u][i]);
        u=fa[u][i];
    }
    if(u==v)return mn;
    for(int i=19;~i;i--)if(fa[u][i]!=fa[v][i]){
        mn=min(mn,up1[u][i]);
        mn=min(mn,up1[v][i]);
        u=fa[u][i],v=fa[v][i];
    }
    mn=min(mn,up1[u][0]);
    mn=min(mn,up1[v][0]);
    return mn;
}
int query2(int u,int v){
    int mn=inf2;
    if(dep[u]<dep[v])swap(u,v);
    for(int i=19;~i;i--)if(dep[fa[u][i]]>=dep[v]){
        mn=min(mn,up2[u][i]);
        u=fa[u][i];
    }
    if(u==v)return mn;
    for(int i=19;~i;i--)if(fa[u][i]!=fa[v][i]){
        mn=min(mn,up2[u][i]);
        mn=min(mn,up2[v][i]);
        u=fa[u][i],v=fa[v][i];
    }
    mn=min(mn,up2[u][0]);
    mn=min(mn,up2[v][0]);
    return mn;
}
void clear(){
    cnt=0;
    for(int i=1;i<=n;i++)e[i].clear();
    for(int i=0;i<=n;i++){
        memset(fa[i],0,sizeof(fa[i]));
        memset(up1[i],127/2,sizeof(up1[i]));
        memset(up2[i],127/2,sizeof(up2[i]));
    }
}
int find(int x){
    return ff[x]==x?x:ff[x]=find(ff[x]);
}
void dfs(int u){
    for(int i=1;i<20;i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
        up1[u][i]=min(up1[u][i-1],up1[fa[u][i-1]][i-1]);
        up2[u][i]=min(up2[u][i-1],up2[fa[u][i-1]][i-1]);
    }
    for(pii x:e[u])if(x.fi!=fa[u][0]){
        fa[x.fi][0]=u;
        dep[x.fi]=dep[u]+1;
        if(x.se&1)up1[x.fi][0]=x.se;
        else up2[x.fi][0]=x.se;
    }
}
void solve(){

    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),w=read();
        E1[i].u=u,E1[i].v=v,E1[i].w=w;
    }
    for(int i=1;i<=n;i++)ff[i]=i;
    sort(E1+1,E1+m+1,[](cs edge&a,cs edge &b){return a.w<b.w;});
    ll sum=0;int ecnt=0;
    for(int i=1;i<=m;i++){
        int u=find(E1[i].u),v=find(E1[i].v);
        if(u!=v){
            ff[u]=v;sum+=E1[i].w;
            e[E1[i].u].pb(pii(E1[i].v,E1[i].w));
            e[E1[i].v].pb(pii(E1[i].u,E1[i].w));
            ecnt++;
        }
        else{
            E2[++cnt]=E1[i];
        }
    }
    if(ecnt<n-1){
        puts("-1 -1");
        clear();
        return;
    }
    dep[1]=1;
    dfs(1);
    ll sm1=inf,sm2=inf;
    if(sum&1){
        sm1=sum;
        sm2=inf;
        for(int i=1;i<=cnt;i++){
            int u=E2[i].u,v=E2[i].v;
            int x;
            if(E2[i].w&1)x=query2(u,v);
            else x=query1(u,v);
            if(x<=1e9){
                sm2=min(sm2,sum+E2[i].w-x);
            }
        }
    }
    else{
        sm1=inf;
        sm2=sum;
        for(int i=1;i<=cnt;i++){
            int u=E2[i].u,v=E2[i].v;
            int x;
            if(E2[i].w&1)x=query2(u,v);
            else x=query1(u,v);
            if(x<=1e9){
                sm1=min(sm1,sum+E2[i].w-x);
            }
        }
    }
    if(sm1>=inf)sm1=-1;
    if(sm2>=inf)sm2=-1;
    cout<<sm2<<" "<<sm1<<'\n';
    clear();
}

int main(){
    #ifdef Stargazer
    freopen("1.in","r",stdin);
    #endif
    int T=read();
    memset(up1,127/2,sizeof(up1));
    memset(up2,127/2,sizeof(up2));
    while(T--){
        solve();
    }
}