#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5,maxm=5e5+5;
typedef long long ll;
int logg[maxn];
void Init() {
	logg[0]=-1;
	int N=2e5;
	for(int i=1;i<=N;++i) logg[i]=logg[i/2]+1;
}
ll ans,tmp;
int T,n,m;
int f[maxn];
int find(int x) {
	return x==f[x]?x:f[x]=find(f[x]);
}
struct Data{
	int x,y,z;
}a[maxm];
bool comp(Data A,Data B) {
	return A.z<B.z;
}
int Max[2][maxn][20],nxt[maxn][20];
vector<int>qwq[maxn],w[maxn];
int wp[maxn],top[maxn],dep[maxn];
bool vis[maxn];
int siz[maxn],fa[maxn],son[maxn],pos[maxn],rk[maxn],tot;
void clear() {
	for(int i=1;i<=n;++i) {
		qwq[i].clear();
		w[i].clear();
		son[i]=wp[i]=0;
		for(int j=0;j<=1;++j) memset(Max[j][i],0,sizeof(Max[j][i]));
	}
	for(int i=1;i<=m;++i) vis[i]=0;
	tot=0;
}
void dfs1(int u) {
	siz[u]=1;
	for(int i=0;i<qwq[u].size();++i) {
		int v=qwq[u][i];
		if(v==fa[u]) continue;
		fa[v]=u;
		wp[v]=w[u][i];
		dep[v]=dep[u]+1;
		dfs1(v);
		siz[u]+=siz[v];
		if(!son[u]||siz[v]>siz[son[u]]) son[u]=v;
	}
}
void dfs2(int u,int tp) {
	pos[u]=++tot,rk[tot]=u;
	top[u]=tp;
	if(son[u]) dfs2(son[u],tp);
	for(int i=0;i<qwq[u].size();++i) {
		int v=qwq[u][i];
		if(v!=son[u]&&v!=fa[u]) dfs2(v,v);
	}
}
void solve() {
	for(int i=1;i<=n;++i) {
		Max[wp[rk[i]]&1][i][0]=wp[rk[i]];
		if(i==n) nxt[i][0]=0;
		else nxt[i][0]=rk[i+1];
	}
	for(int j=1;j<=18;++j) {
		for(int i=1;i<=n;++i) {
			for(int k=0;k<=1;++k) 
				Max[k][i][j]=max(Max[k][i][j-1],Max[k][nxt[i][j-1]][j-1]);
			nxt[i][j]=nxt[nxt[i][j-1]][j-1];
		}
	}
}
int query(int l,int r,int p) {
	int x=logg[r-l+1];
	return max(Max[p][l][x],Max[p][r-(1<<x)+1][x]);
}
void update(int p) {
	int x=a[p].x,y=a[p].y;
	int res=0;
	while(top[x]!=top[y]) {
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		res=max(res,query(pos[top[x]],pos[x],!(a[p].z&1)));
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	if(x!=y) res=max(res,query(pos[x]+1,pos[y],!(a[p].z&1)));
	if(res) tmp=min(tmp,ans+a[p].z-res);
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>T;
	Init();
	while(T--) {
		cin>>n>>m;
		for(int i=1;i<=m;++i) cin>>a[i].x>>a[i].y>>a[i].z;
		sort(a+1,a+1+m,comp);
		for(int i=1;i<=n;++i) f[i]=i;
		ans=0,tmp=1e18;
		int js=0,kp=0;
		for(int i=1;i<=m;++i) {
			int x=find(a[i].x),y=find(a[i].y);
			if(x!=y) {
				qwq[a[i].x].push_back(a[i].y);
				qwq[a[i].y].push_back(a[i].x);
				w[a[i].x].push_back(a[i].z);
				w[a[i].y].push_back(a[i].z);
				f[x]=y;
				ans+=a[i].z;
				vis[i]=1;
				if(a[i].z&1) js^=1;
				kp++;
			}
		}
		if(kp!=n-1) {
			clear();
            cout<<"-1 -1 \n";
			continue;
		}
		dfs1(1);
		dfs2(1,1);
		solve();
		for(int i=1;i<=m;++i) {
			if(vis[i]) continue;
			update(i);
		}
		if(js&1) swap(ans,tmp);
		if(ans==1e18) cout<<"-1 ";
		else cout<<ans<<' ';
		if(tmp==1e18) cout<<"-1\n";
		else cout<<tmp<<'\n';
		clear();
	}
	return 0;
}