#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,M=1e5+5,inf=1e12;
struct edge{int u,v,w;}e[M];

int n,m,root,mn[N],fa[N],tp[N],lp[N],tot,ans,spe;
int zl(){
	root=1; tot=0,ans=0;
	for(int i=1;i<=n;i++) mn[i]=fa[i]=tp[i]=lp[i]=0;
	while(1){
		for(int i=1;i<=n;i++) mn[i]=inf,fa[i]=tp[i]=lp[i]=0;
		
		for(int i=1,u,v,w;i<=m;i++) //Step 1
			if(e[i].u!=e[i].v&&(w=e[i].w)<mn[v=e[i].v])
				mn[v]=w,fa[v]=e[i].u;
		mn[root]=0;
		for(int u=1;u<=n;u++){ans+=mn[u];if(mn[u]==inf)return -1;} //Step 2
		
		for(int u=1,v=1;u<=n;u++,v=u){ //Step 3
			while(v!=root&&tp[v]!=u&&!lp[v]) tp[v]=u,v=fa[v];
			if(v!=root&&!lp[v]){
				lp[v]=++tot;
				for(int k=fa[v];k!=v;k=fa[k]) lp[k]=tot;
			}
		}
		if(!tot) return ans; //Step 4
		for(int i=1;i<=n;i++) if(!lp[i]) lp[i]=++tot; //Step 5
		
		for(int i=1;i<=m;i++) //Step 6
			e[i].w-=mn[e[i].v],e[i].u=lp[e[i].u],e[i].v=lp[e[i].v];
		n=tot, root=lp[root], tot=0; //Step 7
	}
}

signed main(){
int T; cin>>T;
while(T--) {
	scanf("%lld%lld",&n,&m);
	for(int i=1,u,v,w;i<=m;i++)
		scanf("%lld%lld%lld",&u,&v,&w),e[i]=(edge){u,v,w};
	printf("%lld\n",zl());
}
	return 0;
}