#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
#define mem(x,y) memset(x,y,sizeof(x))
typedef long long LL;
#define SI(x) scanf("%d",&x)
#define SL(x) scanf("%lld",&x)
#define T_T while(T--)
#define F(i,x) for(i=1;i<=x;i++)
#define PR(x) printf("%d",x)
#define PL(x) printf("%lld",x)
#define p_ printf(" ")
const int MAXN=210;
const int MAXM=30010;
int mp[MAXN][MAXN];
int lx[MAXN],ly[MAXN],usdx[MAXN],usdy[MAXN],link[MAXN];
int N;
bool dfs(int x){
	int i,j;
	usdx[x]=1;
	F(i,N){
		if(!usdy[i]&&lx[x]+ly[i]==mp[x][i]){
			usdy[i]=1;
			if(link[i]==-1||dfs(link[i])){
				link[i]=x;return true;
			}
		}
	}
	return false;
}
int km(){
	mem(ly,0);mem(link,-1);
	int i,j,k;
	F(i,N){
		lx[i]=-INF;
		F(j,N){
			lx[i]=max(lx[i],mp[i][j]);
		}
	}
	F(i,N){
		mem(usdx,0);mem(usdy,0);
		while(!dfs(i)){
			int d=INF;
			F(j,N){
				if(usdx[j]){
					F(k,N)
						if(!usdy[k])
							d=min(d,lx[j]+ly[k]-mp[j][k]);
				}
			}
			F(j,N){
				if(usdx[j])lx[j]-=d;
				if(usdy[j])ly[j]+=d;
			}
			mem(usdx,0);mem(usdy,0);
		}
	}
	int ans=0;
	F(i,N)ans+=lx[i]+ly[i];
	return -ans;
}
void initial(){
	int i,j;
	F(i,N)F(j,N)mp[i][j]=-INF;
}
int main(){
	int T,M;
	SI(T);
	T_T{
		int a,b,c;
		SI(N);SI(M);
		initial();
		while(M--){
			SI(a);SI(b);SI(c);
			if(-c>mp[a][b])mp[a][b]=-c;
		}
		printf("%d\n",km());
	}
	return 0;
}