#include<bits/stdc++.h>
#define pii pair<int,int>
#define mk make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define fo(i,x,y) for(int i=x;i<=y;++i)
#define go(i,x,y) for(int i=x;i>=y;--i)
#define re return
#define co continue
#define sml(x,y) x=min(x,y)
#define big(x,y) x=max(x,y)
#define ll long long
using namespace std;

int read(){
    int x=0,f=1;
    int ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=x*10+(ch^48);
        ch=getchar();
    }
    re x*f;
}

const int N=5e5+5;
const ll INF=1e18;
struct Edge{
    int x,y,v;
    bool operator<(const Edge &A){re v<A.v;}
}e[N];
int n,m,ban[N];

namespace Dsu{
int f[N];
void init(){fo(i,1,n) f[i]=i;}
int fin(int x){re f[x]==x?x:fin(f[x]);}
bool merge(int x,int y){
    int fx=fin(x),fy=fin(y);
    if(fx==fy) re 0;
    f[fx]=fy;
    re 1;
}
}

namespace Tree{
const int inf=1e9;
vector<pii> e[N];
void add(int x,int y,int v){
    e[x].eb(y,v);
    e[y].eb(x,v);
}
int lg[N],fa[N][21],dep[N];
int mx[N][21][2];

void init(){
    fo(i,1,n) fa[i][0]=dep[i]=0,e[i].clear();
}

void dfs(int x){
    dep[x]=dep[fa[x][0]]+1;
    fo(i,1,lg[n]){
        fa[x][i]=fa[fa[x][i-1]][i-1];
        fo(o,0,1) mx[x][i][o]=max(mx[x][i-1][o],mx[fa[x][i-1]][i-1][o]);
    }
    for(auto i:e[x]) if(i.fi!=fa[x][0]){
        fa[i.fi][0]=x;
        mx[i.fi][0][i.se&1]=i.se;
        mx[i.fi][0][(i.se&1)^1]=0;
        dfs(i.fi);
    }
}

int ask(int x,int y,int o){
    if(dep[x]<dep[y]) swap(x,y);
    int ret=0;
    go(i,lg[n],0) if(dep[fa[x][i]]>=dep[y]) big(ret,mx[x][i][o]),x=fa[x][i];
    if(x==y) re ret;
    go(i,lg[n],0) if(fa[x][i]!=fa[y][i]){
        big(ret,mx[x][i][o]),big(ret,mx[y][i][o]);
        x=fa[x][i],y=fa[y][i];
    }
    big(ret,max(mx[x][0][o],mx[y][0][o]));
    re ret;
}
}

void solve(){
    cin>>n>>m;Dsu::init();Tree::init();
    fo(i,1,m) ban[i]=0;
    fo(i,1,m) e[i].x=read(),e[i].y=read(),e[i].v=read();
    sort(e+1,e+1+m);
    ll ans1=0,ans2=INF;
    int cnt=0;
    fo(i,1,m){
        int x=e[i].x,y=e[i].y;
        if(!Dsu::merge(x,y)) co;
        Tree::add(x,y,e[i].v);
        ans1+=e[i].v;
        ban[i]=1;cnt++;
    }
    if(cnt<n-1){puts("-1 -1");re;}
    Tree::dfs(1);
    fo(i,1,m) if(!ban[i]){
        int qwq=Tree::ask(e[i].x,e[i].y,(e[i].v&1)^1);
        if(qwq<=0) co;
        sml(ans2,ans1-qwq+e[i].v);
    }
    if(ans2<INF) assert((ans1&1)^(ans2&1));
    if(ans1&1) swap(ans1,ans2);
    cout<<(ans1<INF?ans1:-1)<<' '<<(ans2<INF?ans2:-1)<<'\n';
}

signed main(){
    fo(i,2,N-1) Tree::lg[i]=Tree::lg[i>>1]+1;
    int T=read();
    while(T--) solve();
    re 0;
}
/*
3
2 1
1 2 5
3 1
1 3 1
4 4
1 2 1
1 3 1
1 4 1
2 4 2
*/