#include<iostream>
#include<algorithm>
#include<stack>
#include<set>
#include<unordered_set>
#include<queue>
#include<deque>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<map>
#include<string>
#include<vector>
#include<array>
#include<functional>
using namespace std;
typedef long long ll;
ll highbit(ll x){
    ll ans=1;
    int num=0;
    while(x){
        x>>=1;
        ans<<=1;
        num++;
    }
    return num;
}
ll lowbit(ll x){
    return x&(-x);
}
long long max(long long a,long long b){
    return a>b?a:b;
}
long long min(long long a,long long b){
    return a>b?b:a;
}
ll gcd(ll x,ll y)
{
    if(y==0)
        return x;
    return gcd(y,x%y);
}
const int maxn=5e5+10;
int ans[maxn];
struct edge{
	int u,v;
	ll val;
    int flag;
    int id;
	bool operator<(const edge&an){
		return val<an.val;
	}
};
vector<int> G[maxn];
vector<ll> W[maxn];
vector<int> ID[maxn];
edge E[maxn];
struct Kruskal{
	int fa[maxn];
    int find(int x){
        return fa[x]==x?x:fa[x]=find(fa[x]);
    }
	void init(int n,int m){
		for(int i=1;i<=n;i++){
			fa[i]=i;
		}
		sort(E+1,E+1+m);
	}
	bool GreatTree(int n,int m){
		n--;
		int l=1;
		while(n--){
			while(l<=m&&find(E[l].u)==find(E[l].v)){
				l++;
			}
            if(l>m){
                return false;
            }
			G[E[l].u].push_back(E[l].v);
            W[E[l].u].push_back(E[l].val);
            ID[E[l].u].push_back(E[l].id);
			G[E[l].v].push_back(E[l].u);
            W[E[l].v].push_back(E[l].val);
            ID[E[l].v].push_back(E[l].id);
            E[l].flag=1;
            fa[find(E[l].u)]=find(E[l].v);
            l++;
		}
        return true;
	}
}Kal;
ll pos[maxn];
struct LCA{
    int dep[maxn],fa[maxn][21];
    int mx[maxn][21];
    int mx1[maxn][21];
    int faid[maxn];
    ll log[21];
    int lca(int a,int b){
        if(a==b){
            return a;
        }
        if(dep[a]<dep[b]){
            int k=a;
            a=b;
            b=k;
        }
        for(int i=19;i>=0;i--){
            if(dep[fa[a][i]]>=dep[b]){
                a=fa[a][i];
            }
            if(dep[a]==dep[b]){
                break;
            }
        }
        if(a==b){
            return a;
        }
        for(int i=19;i>=0;i--){
            if(fa[a][i]!=fa[b][i]){
                a=fa[a][i];
                b=fa[b][i];
            }
        }
        return fa[a][0];
    }
    void dfs(int x,int pre,int d){
        dep[x]=d;
        int nk=0;
        for(auto i:G[x]){
            if(i==pre){
                nk++;
                continue;
            }
            fa[i][0]=x;
            mx[i][0]=W[x][nk];
            if(W[x][nk]%2!=0){
                mx[i][0]=0;
            }
            mx1[i][0]=W[x][nk];
            if(W[x][nk]%2==0){
                mx1[i][0]=0;
            }
            faid[i]=ID[x][nk];
            nk++;
            dfs(i,x,d+1);
        }
        return;
    }
    void init(int n){
        for(int i=0;i<=20;i++){
            for(int j=1;j<=n;j++){
                fa[i][j]=0;
                mx[i][j]=0;
                mx1[i][j]=0;
            }
        }        
        dfs(1,0,0);
        fa[1][0]=0;
        dep[0]=-1;
        for(int i=1;i<20;i++){
            for(int j=1;j<=n;j++){
                if(fa[j][i-1]==0){
                    continue;
                }
                fa[j][i]=fa[fa[j][i-1]][i-1];
                mx[j][i]=max(mx[j][i-1],mx[fa[j][i-1]][i-1]);
                mx1[j][i]=max(mx1[j][i-1],mx1[fa[j][i-1]][i-1]);
            }
        }
        log[0]=1;
        pos[1]=0;
        for(int i=1;i<20;i++){
            log[i]=log[i-1]*2;
            pos[log[i]]=i;
        }       
    }
    int getmx(int a,int b){
        if(a==b){
            return 0;
        }
        int nowdis=dep[a]-dep[b];
        int buff;
        int ans=0;
        for(int i=20;i>=0;i--){
            if((1<<i)&nowdis){
                ans=max(ans,mx[a][pos[1<<i]]);
                a=fa[a][pos[1<<i]];
            }
        }
        return ans;
    }
    int getmx1(int a,int b){
        if(a==b){
            return 0;
        }
        int nowdis=dep[a]-dep[b];
        int buff;
        int ans=0;
        for(int i=20;i>=0;i--){
            if((1<<i)&nowdis){
                ans=max(ans,mx1[a][pos[1<<i]]);
                a=fa[a][pos[1<<i]];
            }
        }
        return ans;
    }
}Lca0;
int T(void){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>E[i].u>>E[i].v>>E[i].val;
        E[i].id=i;
        E[i].flag=0;
    }
    Kal.init(n,m);
    if(!Kal.GreatTree(n,m)){
        cout<<-1<<" "<<-1<<endl;
        return 0;
    }
    Lca0.init(n);
    ll ans=0;
    for(int i=1;i<=m;i++){
        if(E[i].flag==1){
            ans+=E[i].val;
        }
    }
    ll diff=1e17;
    for(int i=1;i<=m;i++){
        if(E[i].flag==0){
            int u=E[i].u;
            int v=E[i].v;
            ll now=0;
            int fa=Lca0.lca(u,v);
            if(E[i].val%2==1){
                now=max(Lca0.getmx(u,fa),Lca0.getmx(v,fa));
            }else{
                now=max(Lca0.getmx1(u,fa),Lca0.getmx1(v,fa));
            }
            if(now==0){
                continue;
            }
            diff=min(diff,E[i].val-now);
        }
    }
    ll ans2=ans+diff;
    if(ans%2==0){
        cout<<ans<<" ";
        if(ans2>=1e17){
            cout<<-1<<endl;
        }else{
            cout<<ans2<<endl;
        }
    }else{
        if(ans2>=1e17){
            cout<<-1<<" ";
        }else{
            cout<<ans2<<" ";
        }
        cout<<ans<<endl;
    }
    for(int i=1;i<=n;i++){
        G[i].clear();
        W[i].clear();
        ID[i].clear();
    }
    return 0;
}
int main(void){
    unsigned int t;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.in","r",stdin);
    cin>>t;
    //t=1;
    while(t--){
        T();
    }
    return 0;
}