#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];
int pre[N][20],f[2][N][20];
int dep[N];
void dfs(int x,int fa,int prew,int Dep)
{
    dep[x]=Dep;
    f[0][x][0]=f[1][x][0]=-2147483647;
    pre[x][0]=fa;
    if (x!=1)
    { if (prew&1)f[1][x][0]=prew; else f[0][x][0]=prew; }
    for(int i=1;i<=20;i++)pre[x][i]=pre[pre[x][i-1]][i-1];
    for(int i=1;i<=20;i++)
    for(int j=0;j<=1;j++)
        f[j][x][i]=max(f[j][x][i-1],f[j][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=-2147483647;
    if (dep[x]<dep[y])swap(x,y);
    for(int i=20;i>=0;i--)
        if (dep[pre[x][i]]>=dep[y])
        {
            ret=max(ret,f[sign][x][i]);
            x=pre[x][i];
        }
    for(int i=20;i>=0;i--)
        if (pre[x][i]!=pre[y][i])
        {
            ret=max(ret,f[sign][x][i]);
            ret=max(ret,f[sign][y][i]);
            x=pre[x][i];
            y=pre[y][i];
        }
    if (x!=y)
    {
        ret=max(ret,f[sign][x][0]);
        ret=max(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)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,a[i].w));
            g[a[i].y].pb(mp(a[i].x,a[i].w));
            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; }
        for(int i=0;i<=20;i++)f[0][0][i]=f[1][0][i]=-2147483647;
        long long sum2=2147483647ll*10000000ll;
        dfs(1,0,0,1);
        for(auto i:q)
        {
            int t=get(a[i].x,a[i].y,(a[i].w&1)^1);
            //cout<<t<<endl;
            if (t==-2147483647)continue;
            sum2=min(sum2,sum1-t+a[i].w);
        }
        if (sum2==2147483647ll*10000000ll)sum2=-1;
        if (sum1%2==1)swap(sum1,sum2);
        printf("%lld %lld\n",sum1,sum2);
    }
    return 0;
}