#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f3f3f3f3f;
int n,m;
vector<pair<int,int> > e[200005];
struct ss{
    int u,v,w;
    bool operator <(const ss ot)const{
        return w<ot.w;
    }
}a[500005];
int f[200005][18],mx[2][200005][18],d[200005];
int fa[200005];
int find(int x)
{
    if(x==fa[x])return x;
    return fa[x]=find(fa[x]);
}
int ans[2],vis[500005];
bool merge(int u,int v)
{
    u=find(u);v=find(v);
    if(u==v)return 0;
    fa[u]=v;
    return 1;
}
void dfs(int x,int ffa,int w)
{
    f[x][0]=ffa;
    mx[w&1][x][0]=w;
    mx[!(w&1)][x][0]=-inf;
    d[x]=d[ffa]+1;
    for(int i=1;i<=17;i++)
    {
        f[x][i]=f[f[x][i-1]][i-1];
        mx[0][x][i]=max(mx[0][x][i-1],mx[0][f[x][i-1]][i-1]);
        mx[1][x][i]=max(mx[1][x][i-1],mx[1][f[x][i-1]][i-1]);
    }
    for(auto [y,nw]:e[x])
    {
        if(y==ffa)continue;
        dfs(y,x,nw);
    }
}
int getmx(int u,int v,int typ)
{
    if(d[u]<d[v])
        swap(u,v);
    int nmx=-inf;
    for(int i=17;i>=0;i--)
        if(d[f[u][i]]>=d[v])
        {
            nmx=max(mx[typ][u][i],nmx);
            u=f[u][i];
        }
    if(u==v)return nmx;
    for(int i=17;i>=0;i--)
    {
        if(f[u][i]!=f[v][i])
        {
            nmx=max(mx[typ][u][i],nmx);
            nmx=max(mx[typ][v][i],nmx);
            u=f[u][i];v=f[v][i];
        }
    }
    nmx=max(mx[typ][u][0],nmx);
    nmx=max(mx[typ][v][0],nmx);
    return nmx;
}
void solve(void)
{
    cin>>n>>m;
    ans[0]=ans[1]=-1;
    for(int i=1;i<=n;i++)
        e[i].clear(),fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i].u>>a[i].v>>a[i].w;
        vis[i]=0;
    }
    sort(a+1,a+m+1);
    int cnt=n;
    int sum=0;
    for(int i=1;i<=m;i++)
    {
        vis[i]=merge(a[i].u,a[i].v);
        if(vis[i])
        {
            e[a[i].u].push_back(make_pair(a[i].v,a[i].w));
            e[a[i].v].push_back(make_pair(a[i].u,a[i].w));
            cnt--;sum+=a[i].w;
        }
    }
    if(cnt==1)
    {
        dfs(1,0,0);
        int t=sum&1;
        ans[t]=sum;
        for(int i=1;i<=m;i++)
        {
            if(!vis[i])
            {
                int now=getmx(a[i].u,a[i].v,(a[i].w&1)^1);
                if(now!=-inf)
                    ans[t^1]=max(ans[t^1],sum+a[i].w-now);
            }
        }
    }
    cout<<ans[0]<<" "<<ans[1]<<'\n';
}
signed main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}