#include<bits/stdc++.h>
using namespace std;
#define Endl '\n'
#define ll long long
#define int ll
#define ls first
#define rs second
#define pii pair<int,int>
#define pb push_back
const int N=2e5+3;
const int LOGN=19;
const int INF=2e9;
int n,m;
int pre[N];
int dep[N];
int odd[LOGN+1][N],even[LOGN+1][N];
int fa[LOGN+1][N];
vector<array<int,3>> E;
vector<pii> e[N];
map<pii,int> mp;
void init(int n)
{
for(int i=1;i<=n;i++)
{
pre[i]=i;
}
}
int find(int x)
{
if(pre[x]==x)
{
return x;
}
return pre[x]=find(pre[x]);
}
bool join(int x,int y)
{
int fx=find(x),fy=find(y);
if(fx!=fy)
{
pre[fx]=fy;
return 1;
}
return 0;
}
void dfs(int u,int f)
{
dep[u]=dep[f]+1;
for(auto [v,w]:e[u])
{
if(v==f)continue;
if(w&1)
{
odd[0][v]=w;
even[0][v]=0;
}
else
{
odd[0][v]=0;
even[0][v]=w;
}
fa[0][v]=u;
dfs(v,u);
}
}
pii LCA(int u,int v)
{
int ODD=0,EVEN=0;
if(dep[u]<dep[v])
{
swap(u,v);
}
for(int i=LOGN;i>=0;i--)
{
if(dep[fa[i][u]]>=dep[v])
{
ODD=max(ODD,odd[i][u]);
EVEN=max(EVEN,even[i][u]);
u=fa[i][u];
}
}
if(u==v)
{
return {ODD,EVEN};
}
for(int i=LOGN;i>=0;i--)
{
if(fa[i][u]!=fa[i][v])
{
ODD=max({ODD,odd[i][u],odd[i][v]});
EVEN=max({EVEN,even[i][u],even[i][v]});
u=fa[i][u];
v=fa[i][v];
}
}
ODD=max(ODD,odd[0][u]);
EVEN=max(EVEN,even[0][u]);
return {ODD,EVEN};
}
void Clear(int n) {
mp.clear();
E.clear();
for(int i=0;i<=n;i++)
{
e[i].clear();
dep[i]=0;
pre[i]=0;
}
for(int i=0;i<=LOGN;i++)
{
for(int j=0;j<=n;j++)
{
odd[i][j]=0;
even[i][j]=0;
fa[i][j]=0;
}
}
}
void solve()
{
cin>>n>>m;
init(n);
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
if(u>v)
{
swap(u,v);
}
E.pb({w,u,v});
}
sort(E.begin(),E.end());
ll ans=0;
int cnt=0;
for(auto [w,u,v]:E)
{
if(join(u,v))
{
mp[{u,v}]=w;
ans+=w;
e[u].pb({v,w});
e[v].pb({u,w});
cnt++;
}
}
if(cnt<n-1)
{
cout<<"-1 -1"<<Endl;
Clear(n);
return;
}
dfs(1,0);
for(int i=1;i<=LOGN;i++)
{
for(int j=1;j<=n;j++)
{
odd[i][j]=max(odd[i-1][j],odd[i-1][fa[i-1][j]]);
even[i][j]=max(even[i-1][j],even[i-1][fa[i-1][j]]);
fa[i][j]=fa[i-1][fa[i-1][j]];
}
}
ll res=INF;
for(auto [w,u,v]:E)
{
if(mp.count({u,v}))
{
int ww=(*now).rs;
if(ww==w)
{
continue;
}
if((w-ww)%2==0)
{
continue;
}
res=min(res,w-ww);
continue;
}
auto [ODD,EVEN]=LCA(u,v);
if(w%2==1&&EVEN!=0)
{
res=min(res,w-EVEN);
}
else if((w&1)%2==0&&ODD!=0)
{
res=min(res,w-ODD);
}
}
if(res==INF)
{
res=-1;
}
if(ans&1)
{
cout<<(res==-1?res:(res+ans))<<" "<<ans<<Endl;
}
else
{
cout<<ans<<" "<<(res==-1?res:(res+ans))<<Endl;
}
Clear(n);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int _=1;
cin>>_;
while(_--)
{
solve();
}
return 0;
}