#include <bits/stdc++.h>
#define rep(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define stack stck
using namespace std;
#define inf 998244353
#define N 210000
#define M 510000
int n,m;
struct Edge
{
    int x,y,w;
    friend bool operator <(Edge x,Edge y)
    {
        return x.w<y.w;
    }
}a[M];
int father[N];
vector<pair<int,int> > g[N];
void upd(int &x,int y)
{
    if (x==0)x=y;
    else if (y!=0 && a[x].w<a[y].w)x=y;
}
int pre[N][20],f[2][N][20];
int dep[N];
void dfs(int x,int fa,int id,int Dep)
{
    dep[x]=Dep;
    if (pre!=0)
    {
        int t=(a[id].w&1);
        f[t][x][0]=id;
        f[t^1][x][0]=0;
        pre[x][0]=fa;
        for(int i=1;i<=20;i++)
        {
            pre[x][i]=pre[pre[x][i-1]][i-1];
            upd(f[0][x][i],f[0][x][i-1]);
            upd(f[0][x][i],f[0][pre[x][i-1]][i-1]);
            upd(f[1][x][i],f[1][x][i-1]);
            upd(f[1][x][i],f[1][pre[x][i-1]][i-1]);
        }   
    }
    for(auto p:g[x])
        if (p.first!=fa)dfs(p.first,x,p.second,Dep+1);
}
int get(int x,int y,int sign)
{
    int ret=0;
    if (dep[x]<dep[y])swap(x,y);
    for(int i=20;i>=0;i--)
        if (dep[pre[x][i]]>=dep[y])
        {
            upd(ret,f[sign][x][i]);
            x=pre[x][i];
        }
    for(int i=20;i>=0;i--)
        if (pre[x][i]!=pre[y][i])
        {
            upd(ret,f[sign][x][i]);
            upd(ret,f[sign][y][i]);
            x=pre[x][i];
            y=pre[y][i];
        }
    if (x!=y)
    {
        upd(ret,f[sign][x][0]);
        upd(ret,f[sign][y][0]);
    }
    return ret; 
}  
int getfather(int x)
{
    if (father[x]==x)return x;
    return father[x]=getfather(father[x]);
}
int main()
{
    int T;
    cin>>T; 
    while (T--)
    {
        scanf("%d%d",&n,&m);
        rep(i,m)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
        
        sort(a+1,a+m+1);
        rep(i,n)father[i]=i;
        rep(i,n)for(int j=0;j<=20;j++)f[0][i][j]=f[1][i][j]=pre[i][j]=0;
        rep(i,n)g[i].clear();
        vector<int> q; q.clear();
        long long sum1=0; int cnt=0;
        rep(i,m)
        {
            int t1=getfather(a[i].x);
            int t2=getfather(a[i].y);
            if (t1==t2){ q.pb(i); continue; }
            g[a[i].x].pb(mp(a[i].y,i));
            g[a[i].y].pb(mp(a[i].x,i));
            father[t1]=t2;
            sum1=sum1+a[i].w;
            cnt++;
            //cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].w<<endl;
        }   
        if (cnt!=n-1){ puts("-1 -1"); continue; }

        long long sum2=2147483647ll*10000000ll;
        dfs(1,0,0,0);
        for(auto i:q)
        {
            int t=get(a[i].x,a[i].y,(a[i].w&1)^1);
            //cout<<t<<endl;
            if (t==0)continue;
            sum2=min(sum2,sum1-a[t].w+a[i].w);
        }
        if (sum2==2147483647ll*10000000ll)sum2=-1;
        if (sum1%2==1)swap(sum1,sum2);
        printf("%lld %lld\n",sum1,sum2);
    }
    return 0;
}