#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 solve()
{
    cin>>n>>m;
    mp.clear();
    E.clear();
    init(n);
    for(int i=0;i<=n;i++)
    {
        e[i].clear();
        dep[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;
        }
    }
    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;
        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)
    {
        auto now=mp.find({u,v});
        if(now!=mp.end())
        {
            int ww=(*now).rs;
            if(ww==w)
            {
                continue;
            }
            if(!((w-ww)&1))
            {
                continue;
            }
            res=min(res,w-ww);
            continue;
        }
        auto [ODD,EVEN]=LCA(u,v);
        if((w&1)&&EVEN)
        {
            res=min(res,w-EVEN);
        }
        else if(!(w&1)&&ODD)
        {
            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;
        
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _=1;
    cin>>_;

    while(_--)
    {
        solve();
    }
    return 0;
}