#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3fll
#define P make_pair
using namespace std;
int T;
int n,m;
ll ans[2],now;
vector<pair<int,int> > road[200011];
pair<int ,pair<int,int>>  s[2][500011];
int cnt[2];
priority_queue<pair<int ,pair<int,int>> > pq;
int bz[200011][22],mx[2][200011][22],dep[200011];
int fa[200011];
int find_(int x)
{
    return fa[x]=fa[x]==x?x:find_(fa[x]);
}
void dfs(int x,int f,int v)
{
    dep[x]=dep[f]+1;
    bz[x][0]=f;
    mx[v%2][x][0]=v;
    for(int t=1;t<=21;++t)
    {
        bz[x][t]=bz[bz[x][t-1]][t-1];
        mx[0][x][t]=max(mx[0][x][t-1],mx[0][bz[x][t-1]][t-1]);
        mx[1][x][t]=max(mx[1][x][t-1],mx[1][bz[x][t-1]][t-1]);
    }
    for(auto v:road[x])
    {
        if(v.first==f) continue;
        dfs(v.first,x,v.second);
    }
}
int check(int x,int y,int opt)
{
    if(dep[x]<dep[y]) swap(x,y);
    int ret=0;
    for(int i=21;i>=0;--i)
    {
        if(dep[bz[x][i]]>=dep[y])
        {
            ret=max(ret,mx[opt][x][i]);
            x=bz[x][i];
        }
    }
    if(x==y) return ret;
    for(int i=21;i>=0;--i)
    {
        if(bz[x][i]!=bz[y][i])
        {
            ret=max(ret,mx[opt][x][i]);
            ret=max(ret,mx[opt][y][i]);
            x=bz[x][i];
            y=bz[y][i];
        }
    }
    ret=max(ret,max(mx[opt][x][0],mx[opt][y][0]));
    return ret;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=1,u,v,w;i<=m;++i)
        {
            cin>>u>>v>>w;
            pq.push(P(-w,P(u,v)));
        }
        for(int i=1;i<=n;++i) fa[i]=i,road[i].clear(),dep[i]=0;
        now=0;
        ans[0]=ans[1]=inf;
        int tot=n;
        cnt[0]=cnt[1]=0;
        for(int t=0;t<2;++t)
        {
            for(int i=1;i<=n;++i)
            {
                for(int j=0;j<=21;++j)
                {
                    bz[i][j]=mx[t][i][j]=0;
                }
            }
        }
        while(pq.size())
        {
            int a=-pq.top().first,u=pq.top().second.first,v=pq.top().second.second;
            pq.pop();
            if(find_(u)!=find_(v))
            {
                fa[find_(u)]=find_(v);
                road[u].push_back(P(v,a));
                tot--;
                now+=a;
            }
            else
            {
                s[a%2][++cnt[a%2]]=P(a,P(u,v));
                // cout<<a%2<<"     "<<a<<"  "<<u<<" "<<v<<endl;
            }
        }
        // cout<<tot<<" ada wd  "<<now<<endl;
        if(tot!=1)
        {
            cout<<-1<<" "<<-1<<endl;
        }
        else
        {
            ans[now%2]=now;
            dfs(1,1,0);
            for(int t=0;t<2;++t)
            for(int i=1;i<=cnt[t];++i)
            {
                int mx=check(s[t][i].second.first,s[t][i].second.second,t^1);
                // cout<<(t^1)<<" "<<s[t][i].second.first<<" "<<s[t][i].second.second<<" "<<"      "<<mx<<endl;
                if(mx) ans[!(now%2)]=min(ans[!(now%2)],now-mx+s[t][i].first);
            }
            if(ans[0]==inf) ans[0]=-1;
            if(ans[1]==inf) ans[1]=-1;
            cout<<ans[0]<<" "<<ans[1]<<endl;
        }
    }
    return 0;
}