#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MaxN=200000+10;
int n,m,u,v,c,ans,mnde,bel[MaxN],sm,t;
int fa[MaxN][21],dep[MaxN],mx[MaxN][21][2];
vector<pair<int,int>>V[MaxN];
priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<tuple<int,int,int>>>Q,Q2;
//doublizing
int find(int x){
return (bel[x]==x?x:bel[x]=find(bel[x]));
}
void dfs(int u,int faa){
for(int i=1;fa[u][i-1]>0;i++){
fa[u][i]=fa[fa[u][i-1]][i-1];
mx[u][i][0]=max(mx[u][i-1][0],mx[fa[u][i-1]][i-1][0]);
mx[u][i][1]=max(mx[u][i-1][1],mx[fa[u][i-1]][i-1][1]);
}
for(auto [v,c]:V[u]){
if(v==faa)continue;
fa[v][0]=u;
mx[v][0][c%2]=c;
dep[v]=dep[u]+1;
dfs(v,u);
}
}
int lca(int a,int b,bool c){
if(dep[a]<dep[b])swap(a,b);
int delp=dep[a]-dep[b],res=-1;
for(int i=20;i>=0;i--){
if(delp&(1<<i)){
res=m,max(res,mx[a][i][c]);
a=fa[a][i];
}
}
if(a==b)return res;
for(int i=20;i>=0;i--){
if(fa[a][i]!=fa[b][i]){
res=max(res,max(mx[a][i][c],mx[b][i][c]));
a=fa[a][i];
b=fa[b][i];
}
}
res=max(res,max(mx[a][0][c],mx[b][0][c]));
return res;
}
void solve(){
for(int i=1;i<=n;i++)V[i].clear();
memset(mx+1,-1,sizeof(mx[0])*n);
memset(fa+1,0,sizeof(fa[0])*n);
// memset(mx,-1,sizeof(mx));
// memset(fa,-1,sizeof(fa));
mnde=1000000000ll,ans=sm=0;
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>u>>v>>c;
if(u==v)continue;
Q.emplace(c,u,v);
}
for(int i=1;i<=n;i++)bel[i]=i;
while(!Q.empty()){
auto [c,u,v]=Q.top();Q.pop();
int a=find(u),b=find(v);
if(a==b){
Q2.emplace(c,u,v);//unchosen edge
continue;
}
bel[a]=b;
ans+=c;sm++;
V[u].emplace_back(v,c);//build tree
V[v].emplace_back(u,c);
}
if(sm+1<n){
cout<<"-1 -1"<<endl;
return ;
}
dfs(1,0);//f**king init for LCA
while(!Q2.empty()){
auto [c,u,v]=Q2.top();Q2.pop();
int del=lca(u,v,1-c%2));
if(del>0)mnde=min(mnde,c-del);
}
if(mnde>=1000000000ll){
if(ans%2)cout<<"-1 "<<ans<<endl;
else cout<<ans<<" -1"<<endl;
}else{
if(ans%2)cout<<mnde+ans<<" "<<ans<<endl;
else cout<<ans<<" "<<mnde+ans<<endl;
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--){
solve();
}
}