#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
#define int long long 
#define FT first
#define SD second
const int N=200009;
int n,m,t,cnt;
pair<int,PII> e[N];
vector<PII> a[N];
vector<int> b;
int fa[N],vis[N],f[22][N],mx_od[22][N],mx_ev[22][N],dep[N];
LL ans,uans;
int find(int x)
{
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}
void merge(int x,int y)
{
    fa[find(x)]=y;
}
void dfs(int x,int fa)
{
    f[0][x]=fa;
    dep[x]=dep[fa]+1;
    for(PII i:a[x])
    {
        if(i.FT==fa) continue;
        if(i.SD%2) mx_od[0][i.FT]=i.SD;
        else mx_ev[0][i.FT]=i.SD;
    }
}
signed main()
{
    scanf("%lld",&t);
    while(t--)
    {
        ans=cnt=0;
        scanf("%lld%lld",&n,&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%lld%lld%lld",&e[i].SD.FT,&e[i].SD.SD,&e[i].FT);
        }
        sort(e+1,e+m+1);
        for(int i=1;i<=n;i++) fa[i]=i;
        for(int i=1;i<=m;i++)
        {
            if(find(e[i].SD.FT)!=find(e[i].SD.SD))
            {
                merge(e[i].SD.FT,e[i].SD.SD),ans+=e[i].FT,cnt++;
                a[e[i].SD.FT].emplace_back(e[i].SD.SD,e[i].FT);
                a[e[i].SD.SD].emplace_back(e[i].SD.FT,e[i].FT);
            }
            else b.push_back(i);
        }
        for(int i=1;i<=n;i++) vis[i]=0;
        if(cnt==n-1)
        {
            uans=0x3f3f3f3f3f3f+ans;
            mx_od[0][1]=mx_ev[0][1]=0;
            dfs(1,1);
            for(int i=1;i<=20;i++)
                for(int j=1;j<=n;j++)
                {
                    f[i][j]=f[i-1][f[i-1][j]];
                    mx_od[i][j]=max(mx_od[i-1][j],mx_od[i-1][f[i-1][j]]);
                    mx_ev[i][j]=max(mx_ev[i-1][j],mx_ev[i-1][f[i-1][j]]);
                }
            for(int i:b)
            {
                if(e[i].FT%2)
                {
                    int x=e[i].SD.FT,y=e[i].SD.SD,oans=0;
                    if(dep[y]>dep[x]) swap(x,y);
                    if(dep[x]!=dep[y])
                    {
                        for(int i=20;~i;i--)
                        {
                            if(dep[y]+(1<<i)>=dep[x]) oans=max(oans,mx_ev[i][x]),x=f[i][x];
                        }
                    }
                    if(x!=y)
                    {
                        for(int i=20;~i;i--)
                        {
                            if(f[i][x]!=f[i][y])
                                oans=max({oans,mx_ev[i][x],mx_ev[i][y]}),x=f[i][x],y=f[i][y];
                        }
                        oans=max({oans,mx_ev[0][x],mx_ev[0][y]});
                    }
                    uans=min(uans,ans-oans+e[i].FT);
                }
                else
                {
                    int x=e[i].SD.FT,y=e[i].SD.SD,oans=0;
                    if(dep[y]>dep[x]) swap(x,y);
                    if(dep[x]!=dep[y])
                    {
                        for(int i=20;~i;i--)
                        {
                            if(dep[y]+(1<<i)>=dep[x]) oans=max(oans,mx_od[i][x]),x=f[i][x];
                        }
                    }
                    if(x!=y)
                    {
                        for(int i=20;~i;i--)
                        {
                            if(f[i][x]!=f[i][y])
                                oans=max({oans,mx_od[i][x],mx_od[i][y]}),x=f[i][x],y=f[i][y];
                        }
                        oans=max({oans,mx_od[0][x],mx_od[0][y]});
                    }
                    uans=min(uans,ans-oans+e[i].FT);
                }
            }
            if(uans-ans>2e9) uans=-1;
            if(ans%2==0) printf("%lld %lld\n",ans,uans);
            else printf("%lld %lld\n",uans,ans);
        }
        else printf("-1 -1\n");
        for(int i=1;i<=n;i++) a[i].clear();
    }
}
/*
3
2 1
1 2 5
3 1
1 3 1
4 4
1 2 1
1 3 1
1 4 1
2 4 2
  
 */