#include "iostream"
#include "cstring"
#include "cstdio"
#include "algorithm"
#include "queue"
#include "vector"
#include "queue"
#include "stack"
#include "ctime"
#include "set"
#include "map"
#include "cmath"
using namespace std;
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define mp make_pair
#define rep( i , a , b ) for( int i = (a) , i##end = b ; i <= i##end ; ++ i )
#define per( i , a , b ) for( int i = (a) , i##end = b ; i >= i##end ; -- i )
#define mem( a ) memset( a , 0 , sizeof (a) )
#define all( x ) x.begin() , x.end()
//#define int long long
typedef long long ll;
const int MAXN = 2e5 + 10;
int n , m;

struct ed {
	int u , v , w;
	void in( ) {
		scanf("%d%d%d",&u,&v,&w);
	}
	bool operator < ( const ed& t ) {
		return w > t.w;
	}
} E[MAXN] ;

int head[MAXN] , to[MAXN << 1] , nex[MAXN << 1] , wto[MAXN << 1] , ecn;
void ade( int u , int v , int w ) {
	to[++ ecn] = v , nex[ecn] = head[u] , wto[ecn] = w , head[u] = ecn;
	to[++ ecn] = u , nex[ecn] = head[v] , wto[ecn] = w , head[v] = ecn;
}
int dep[MAXN] , cur[MAXN];
vi poi;
const int inf = 1e9;
bool bfs( int s , int t ) {
	queue<int> Q;
	Q.push( s );
	for( int x : poi ) cur[x] = head[x] , dep[x] = 0x3f3f3f3f;
	dep[s] = 0;
	while( !Q.empty() ) {
		int u = Q.front(); Q.pop( );
		for( int i = head[u] ; i ; i = nex[i] ) if( dep[to[i]] > inf && wto[i] )
			dep[to[i]] = dep[u] + 1 , Q.push( to[i] );
	}
	return dep[t] < inf;
}
int dfs( int u , int lim , int t ) {
	if( !lim || u == t ) return lim;
	int flow = 0 , f;
	for( int& i = cur[u] ; i ; i = nex[i] ) if( dep[to[i]] == dep[u] + 1 && ( f = dfs( to[i] , min( lim , wto[i] ) , t ) ) ) {
		lim -= f , flow += f , wto[i] -= f , wto[i ^ 1] += f;
		if( !lim ) break;
	}
	return flow;
}

int deg[MAXN];
int dinic( int s , int t ) {
	int res = 0;
	while( bfs( s , t ) ) 
		res += dfs( s , deg[s] , t );
	return res;
}

vi G[MAXN];
int vis[MAXN];


void afs( int u ) {
	vis[u] = 1 , poi.pb( u );
	for( int v : G[u] ) {
		if( u < v ) 
			ade( u , v , 1 );
		if( !vis[v] ) afs( v );
	}
}

int fa[MAXN];
int find( int x ) {
	return x == fa[x] ? x : fa[x] = find( fa[x] );
}

void solve() {
	cin >> n >> m;
	rep( i , 1 , m ) {
		E[i].in();
	} 
	sort( E + 1 , E + 1 + m );
	int res = 0x3f3f3f3f;
	rep( i , 1 , n ) fa[i] = i;
	rep( i , 1 , m ) {
		int j = i;
		while( j <= m && E[i].w == E[j].w ) ++ j;
		-- j;
//		cout << i << ' ' << j << endl;
		vi nod;
		rep( t , i , j ) {
			int u = find( E[t].u ) , v = find( E[t].v );
			if( u == v ) continue;
			nod.pb( u ) , nod.pb( v );
			G[u].pb( v ) , G[v].pb( u );
			++ deg[u] , ++ deg[v];
		}
		sort( all( nod ) ) , nod.erase( unique( all( nod ) ) , nod.end() );
		for( int u : nod ) if( !vis[u] ) {
			ecn = 1;
			afs( u );
			sort( all( poi ) , [&]( int a , int b ) { return deg[a] < deg[b]; } );
			int s = poi[0];
			rep( i , 1 , poi.size() - 1 ) {
				res = min( res , dinic( s , poi[i] ) );
				rep( t , 2 , ecn ) wto[t] = 1;
			}
			for( int x : poi ) head[x] = 0;
			poi.clear();
		}
		for( int x : nod ) G[x].clear() , deg[x] = vis[x] = 0;
		rep( t , i , j ) {
			int u = find( E[t].u ) , v = find( E[t].v );
			if( u == v ) continue;
			fa[u] = v;
		}
		i = j;
	}
	cout << res << endl;
}

signed main() {
//	freopen("in","r",stdin);
//	freopen("out","w",stdout);
	int T;cin >> T;while( T-- ) solve();
//	solve();
}