#include<bits/stdc++.h>
using namespace std;
int n;
int oi[18][18],wc[18];
vector<int>g[18];
#define pb push_back
vector<int>st[1<<20];
void dfs(int x,int f,int S,int u){
	if(f!=-1)st[u].pb(S);
	for(int v:g[x])if(v!=f){
		int w=oi[x][v];
		if(wc[w]!=1)dfs(v,x,S|(1<<w),u<<1);
		if(wc[w]!=0)dfs(v,x,S|(1<<w),u<<1|1);
	}
}
int js[1<<21],E,le[1<<21],sv[1<<21];
void pr(int x,int d){
	if(d==n)return;
	for(int o:st[x])
		js[++E]=o,le[E]=d,sv[E]=x;
	pr(x<<1,d+1),pr(x<<1|1,d+1);
}
const int I=1e9;
int dp[1<<17][20];
vector<int>o[20];
void ad(int &x,int y){x=max(x,y);}
int jb(int u,int v){
	while(u!=v){
		if(u>v)swap(u,v);
		v>>=1;
	}
	int d=0;
	while(u>1)u>>=1,d++;
	return d;
}
void sol(){
	memset(oi,0,sizeof(oi));
	scanf("%d",&n);
	for(int i=0;i<(1<<n);i++)st[i].clear();
	for(int i=0;i<n;i++)g[i].clear();
	for(int i=0,u,v;i+1<n;i++){
		scanf("%d%d%d",&u,&v,&wc[i]);
		oi[u][v]=oi[v][u]=i;
		g[u].pb(v),g[v].pb(u);
	}
	for(int i=0;i<n;i++)dfs(i,-1,0,1);
	E=0,pr(1,0);n--;
	for(int s=0;s<(1<<n);s++)for(int i=0;i<=n;i++)dp[s][i]=-1;
	for(int i=0;i<=n;i++)o[i].clear();
	dp[0][0]=0,o[0].pb(0);
	for(int i=1;i<=E;i++){
		if(i>1){
			int lc=jb(sv[i],sv[i-1]);
			for(int j=lc+1;j<=n;j++)if(!o[j].empty()){
				for(int so:o[j]){
					if(dp[so][lc]<0)dp[so][lc]=dp[so][j],o[lc].pb(so);
					else ad(dp[so][lc],dp[so][j]);
					dp[so][j]=-1;
				}
				o[j].clear();
			}
		}
		int S=((1<<n)-1)^js[i],s2=S;
		while(1){
			for(int j=0;j<=n;j++)if(dp[s2][j]>=0){
				int zd=dp[s2][j]+le[i]-j;
				if(dp[js[i]|s2][le[i]]<0)dp[js[i]|s2][le[i]]=zd,o[le[i]].pb(js[i]|s2);
				else ad(dp[js[i]|s2][le[i]],zd);
			}
			if(!s2)break;s2=(s2-1)&S;
		}
	}
	int ans=-1;
	for(int s=0;s<(1<<n);s++)for(int i=0;i<=n;i++)ad(ans,dp[s][i]);
	printf("%d\n",ans+1);
}
int main(){
	int T,tt;
	puts("0");
	scanf("%d%d",&T,&tt);while(T--)sol();
	return 0;
}