#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<array>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=500005,INF=1e18;
int t,n,m,fa[N],dep[N],anc[N][20],mx[N][20][2];
array <int,3> E[N]; vector <pair <int,int>> T[N];
inline int getfa(CI x)
{
    return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
inline void DFS(CI now=1,CI fa=0)
{
    dep[now]=dep[fa]+1; anc[now][0]=fa;
    for (RI i=0;i<19;++i)
    if (anc[now][i])
    {
        anc[now][i+1]=anc[anc[now][i]][i];
        for (RI j=0;j<2;++j) mx[now][i+1][j]=max(mx[now][i][j],mx[anc[now][i]][i][j]);
    } else break;
    for (auto [to,w]:T[now]) if (to!=fa)
    {
        mx[to][0][w&1]=w; mx[to][0][(w&1)^1]=INF;
        DFS(to,now);
    }
}
inline int query(int x,int y,CI tp,int ret=0)
{
    if (dep[x]<dep[y]) swap(x,y);
    for (RI i=19;i>=0;--i) if (dep[anc[x][i]]>=dep[y])
    ret=max(ret,mx[x][i][tp]),x=anc[x][i];
    if (x==y) return ret;
    for (RI i=19;i>=0;--i) if (anc[x][i]!=anc[y][i])
    ret=max(ret,max(mx[x][i][tp],mx[y][i][tp])),x=anc[x][i],y=anc[y][i];
    return max(ret,max(mx[x][0][tp],mx[y][0][tp]));
}
signed main()
{
    for (scanf("%lld",&t);t;--t)
    {
        scanf("%lld%lld",&n,&m);
        for (RI i=1;i<=m;++i) scanf("%lld%lld%lld",&E[i][1],&E[i][2],&E[i][0]);
        sort(E+1,E+m+1); vector <array <int,3>> Rep;
        for (RI i=1;i<=n;++i) fa[i]=i,T[i].clear();
        int sum1=0,cnt=0;
        for (RI i=1;i<=m;++i)
        {
            auto [w,u,v]=E[i];
            if (getfa(u)==getfa(v))
            {
                Rep.push_back(E[i]); continue;
            }
            fa[getfa(u)]=getfa(v); sum1+=w; ++cnt;
            T[u].push_back({v,w}); T[v].push_back({u,w});
        }
        if (cnt!=n-1)
        {
            puts("-1 -1"); continue;
        }
        int sum2=INF; DFS();
        for (auto [w,u,v]:Rep)
        {
            int ww=query(u,v,(w&1)^1);
            if (ww!=INF) sum2=min(sum2,sum1-ww+w);
        }
        if (sum1&1) swap(sum1,sum2);
        if (sum1==INF) sum1=-1;
        if (sum2==INF) sum2=-1;
        printf("%lld %lld\n",sum1,sum2);
    }
    return 0;
}