#include<bits/stdc++.h>
using namespace std;
int n,cnt;
int E[19][19],id[19][19];
mt19937 rd(time(0));
struct node{
	int eset,num,st,ed;
	int road[19],len;
	void init(int x){
		len=eset=num=0;
		road[0]=st=ed=x;
	}
}path[3005];
bool cmp(node p1,node p2){
	if(p1.num!=p2.num) return p1.num<p2.num;
	if(p1.len!=p2.len) return p1.len<p2.len;
	return p1.eset<p2.eset;
}
void dfs(int u,int fa,node pp,int lim){
	if(u!=pp.st) path[++cnt]=pp;
	for(int v=1;v<=n;v++){
		if(id[u][v]==0||v==fa) continue;
		node go=pp;
		go.road[++go.len]=v;
		go.ed=v;
		go.eset+=(1<<(id[u][v]-1));
		if(lim==0){
			int c=E[u][v];
			if(c==2) c=rd()%2;
			go.num+=c*(1<<(n-go.len));
			dfs(v,u,go,0);
		}
		else{
			if(E[u][v]!=1) dfs(v,u,go,lim-1);
			go.num+=(1<<(n-go.len));
			if(E[u][v]!=0) dfs(v,u,go,lim-1);
		}
	}
}
int f[1<<18|1][19],lcp[3005],up[1<<18|1];
void solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) E[i][j]=id[i][j]=0;
	for(int i=1;i<n;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		u++,v++;
		E[u][v]=E[v][u]=w;
		id[u][v]=id[v][u]=i;
	}
	cnt=0;
	for(int i=1;i<=n;i++){
		node pp;
		pp.init(i);
		dfs(i,0,pp,2);
	}
	sort(path+1,path+cnt+1,cmp);
	for(int i=2;i<=cnt;i++){
		lcp[i]=0;
		for(int j=1;j<=min(path[i-1].len,path[i].len);j++){
			if(path[i-1].num/(1<<(n-j))!=path[i].num/(1<<(n-j))) break;
			lcp[i]=j;
		}
	}
	lcp[1]=n;
	int lim=(1<<(n-1));
	for(int i=0;i<lim;i++){
		for(int j=0;j<n;j++) f[i][j]=-1e9;
		up[i]=-1;
	}
	for(int i=1;i<=cnt;i++){
		if(path[i].num==path[i-1].num&&path[i].eset==path[i-1].eset) continue;
		int s=path[i].eset,len=path[i].len;
		for(int j=lim;j>0;j--){
			while(up[j]>lcp[i]){
				f[j][lcp[i]]=max(f[j][lcp[i]],f[j][up[j]]);
				f[j][up[j]]=-1e9;
				up[j]--;
			}
			if((j&s)==0){
				for(int k=0;k<=lcp[i];k++)
					f[j+s][lcp[i+1]]=max(f[j+s][lcp[i+1]],f[j][k]+len-k);
				up[j+s]=max(up[j+s],lcp[i+1]);
			}
		}
		f[s][lcp[i+1]]=max(f[s][lcp[i+1]],len);
		up[s]=max(up[s],lcp[i+1]);
	}
	int ans=0;
	for(int j=1;j<lim;j++)
		for(int k=0;k<n;k++)
			ans=max(ans,f[j][k]);
	printf("%d\n",ans+1);
}
int main(){
	int t,o;
	scanf("%d%d",&t,&o);
	printf("0\n");
	while(t--) solve();
}