#include<bits/stdc++.h>

using namespace std;

using ll=long long;

const int N=500010;

int n,m;
vector<pair<int,int>> G[N];
int fa[N];
int dep[N];
int F[N][22],W[N][22][2];
void Dfs(int u,int fa)
{
    for(int j=1;j<21;j++)
    {
        F[u][j]=F[F[u][j-1]][j-1];
        W[u][j][0]=min(W[u][j-1][0],W[F[u][j-1]][j-1][0]);
        W[u][j][1]=min(W[u][j-1][1],W[F[u][j-1]][j-1][1]);
    }
    for(auto [v,w]:G[u])
    {
        if(v==fa) continue;
        F[v][0]=u;
        W[v][0][0]=W[v][0][1]=1000000010;
        W[v][0][w%2]=w;
        dep[v]=dep[u]+1;
        Dfs(v,u);
    }
}
int Find(int x)
{
    if(x==fa[x]) return x;
    return fa[x]=Find(fa[x]);
}
int Query(int x,int y,int id)
{
    if(dep[x]<dep[y]) swap(x,y);
    int ret=1000000010;
    for(int j=21;j>=0;j--)
        if(dep[F[x][j]]>=dep[y])
            ret=min(ret,W[x][j][id]),x=F[x][j];
    if(x==y) return ret;
    for(int j=21;j>=0;j--)
        if(F[x][j]!=F[y][j])
        {
            ret=min(ret,W[x][j][id]);
            ret=min(ret,W[y][j][id]);
            x=F[x][j];
            y=F[y][j];
        }
    ret=min(ret,W[x][0][id]);
    ret=min(ret,W[y][0][id]);
    return ret;
}
void Solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        G[i].clear(),fa[i]=i;
    int cnt=0;
    vector<array<int,3>> input(m),edge;
    for(int i=0;i<m;i++)
    {
        auto &[z,x,y]=input[i];
        cin>>x>>y>>z;
    }
    sort(input.begin(),input.end());
    ll Ans=0;
    for(int i=0;i<m;i++)
    {
        auto [z,x,y]=input[i];
        int X=Find(x),Y=Find(y);
        if(X==Y)
        {
            edge.push_back({x,y,z});
            continue;
        }
        G[x].push_back({y,z});
        G[y].push_back({x,z});
        fa[X]=Y;
        Ans+=z;
        cnt++;
    }
    if(cnt<n-1)
    {
        cout<<"-1 -1\n";
        return;
    }
    dep[1]=1;
    Dfs(1,0);
    ll Ans2=10000000000000000;
    for(auto [z,x,y]:edge)
    {
        int ans=Query(x,y,(z%2)^1);
        if(ans>1000000000) continue;
        Ans2=min(Ans2,Ans-ans+z);
    }
    if(Ans2==10000000000000000) Ans2=-1;
    if(Ans%2!=0) swap(Ans,Ans2);
    cout<<Ans<<" "<<Ans2<<"\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--) Solve();
    return 0;
}