#include<bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
using namespace std;
mt19937 rnd(time(0));
int dep[100500],son[100500][2],tot,rt,n;
pii ans[100500];
int id[100500],len[100500],Mask[100500],tt,fa[100500];
vector<pii>road[20];
vector<int>vec[100500];
vector<pii>Vec[100500];
map<pii,int>Mp;
int Rt;
const int inf=1e9;
int f[1<<17][20],d[1<<17][2];
struct Node{int pos,mask,lcp,Preval,lstd;}stk[50005000];
int tail;
void dfs(int u,int f,int p,int d,int m){
	if(p>rt)vec[p].pb(m),Vec[p].pb(mp(Rt,u));
	for(auto v:road[u]){
		if(v.fi==f)continue;
		int id1=Mp[mp(u,v.fi)];
		if(u>v.fi)id1=Mp[mp(v.fi,u)];
		if(v.se<2){
			if(!son[p][v.se])son[p][v.se]=++tot,dep[tot]=dep[p]+1;
			dfs(v.fi,u,son[p][v.se],d+1,(m|(1<<id1-1)));
		}else{
			if(d<2){
				if(!son[p][0])son[p][0]=++tot,dep[tot]=dep[p]+1;
				if(!son[p][1])son[p][1]=++tot,dep[tot]=dep[p]+1;
				dfs(v.fi,u,son[p][0],d+1,(m|(1<<id1-1)));
				dfs(v.fi,u,son[p][1],d+1,(m|(1<<id1-1)));
			}else{
				int o=rnd()%2;
				if(!son[p][o])son[p][o]=++tot,dep[tot]=dep[p]+1;
				dfs(v.fi,u,son[p][o],d+1,(m|(1<<id1-1)));
			}
		}
	}
}
void Dfs(int p){
	for(int i=0;i<vec[p].size();++i){
		auto v=vec[p][i];id[++tt]=p,len[tt]=dep[p],Mask[tt]=v;
		ans[tt]=Vec[p][i];
	}
	if(son[p][0])Dfs(son[p][0]);
	if(son[p][1])Dfs(son[p][1]);
}
int LCP(int p,int q){
	if(dep[p]>dep[q])swap(p,q);
	while(dep[q]>dep[p])q=fa[q];
	while(p!=q)p=fa[p],q=fa[q];
	return dep[p];
}
int ht[20505];
int opr(int x){return son[fa[x]][1]==x;}
int Stk[20],Tail,pw[20];
int stk1[20],tail1;
void dfs1(int u,int f,int t){
	if(tail1==-1)return;
	stk1[++tail1]=u;
	if(u==t){
		for(int i=tail1-1;i>=1;--i)pw[Mp[mp(min(stk1[i],stk1[i+1]),max(stk1[i],stk1[i+1]))]]=Stk[i];
		tail1=-1;
		return;
	}
	for(auto v:road[u]){
		if(tail1==-1)break;
		if(v.fi==f)continue;
		dfs1(v.fi,u,t);
	}
	if(tail1==-1)return;
	--tail1;
}
void solve(){
	scanf("%d",&n),Mp.clear();int tt1=0;
	for(int i=1;i<=n;++i)road[i].clear();
	for(int i=1;i<n;++i){
		int u,v,w;scanf("%d%d%d",&u,&v,&w),pw[i]=w;++u,++v;
		if(u>v)swap(u,v);Mp[mp(u,v)]=++tt1;
		road[u].pb(mp(v,w)),road[v].pb(mp(u,w));
	}
	for(int i=1;i<=tot;++i)son[i][0]=son[i][1]=dep[i]=fa[i]=id[i]=0,vec[i].clear(),Vec[i].clear();
	tot=rt=1,tt=0;
	for(int i=1;i<=n;++i)Rt=i,dfs(i,-1,rt,0,0);
	for(int i=1;i<=tot;++i){
		if(son[i][0])fa[son[i][0]]=i;
		if(son[i][1])fa[son[i][1]]=i;
	}
	Dfs(rt);
	for(int i=0;i<(1<<n-1);++i)for(int j=0;j<=n-1;++j)f[i][j]=-inf,d[i][j]=0;
	f[0][0]=0,tail=0;
	int Ans=-inf,D=0,ed=tt;
	for(int i=1;i<tt;++i)ht[i]=LCP(id[i],id[i+1]);
	for(int i=1;i<=tt;++i){
		int Val=len[i];if(i>1)Val=ht[i-1];
		for(int jk=i-1,mn=len[jk];jk>=1&&mn>Val;mn=min(mn,ht[jk-1]),--jk){
			int now=(((1<<n-1)-1)^Mask[jk]);
			for(int s=now;;s=((s-1)&now)){
				int j=(s|Mask[jk]);
				int mx=-inf,from=-1;
				for(int k=Val;k<n;++k){
					if(f[j][k]<0)continue;
					if(f[j][k]>mx)mx=f[j][k],from=k;
				}
				if(mx>f[j][Val]){
					stk[++tail]=Node{2*i-1,j,Val,f[j][Val],d[j][Val]};
					f[j][Val]=mx,d[j][Val]=from;
				}
				if(!s)break;
			}
		}
		for(int j=0;j<(1<<n-1);++j){
			if(j&Mask[i])continue;
			int Mx=-inf,Now=-1;
			for(int k=0;k<n;++k){
				int res=f[j][k]-k+len[i];
				if(res<0)continue;
			    Mx=max(Mx,res);
			    if(Mx==res)Now=k;
			}
			if(f[j|Mask[i]][len[i]]<Mx){
			    stk[++tail]=Node{2*i,(j|Mask[i]),len[i],f[j|Mask[i]][len[i]],d[j|Mask[i]][len[i]]};
			   	f[j|Mask[i]][len[i]]=Mx,d[j|Mask[i]][len[i]]=Now;
			}
		}
		int ans=0;
		for(int j=0;j<n;++j)ans=max(ans,f[(1<<n-1)-1][j]);
		if(ans==n-1){ed=i;break;}
    }
	for(int i=0;i<n;++i)
		if(Ans<f[(1<<n-1)-1][i])
		  Ans=f[(1<<n-1)-1][i],D=i;
	printf("%d\n",Ans+1);
/*	int Now=(1<<n-1)-1;
	vector<int>Res;
	for(int i=ed;i>=1;--i){
		while(tail&&stk[tail].pos==2*i){
			f[stk[tail].mask][stk[tail].lcp]=stk[tail].Preval;
			d[stk[tail].mask][stk[tail].lcp]=stk[tail].lstd;
			--tail;
		}
		Tail=0;
		for(int j=id[i];j>rt;j=fa[j])Stk[++Tail]=opr(j);
		reverse(Stk+1,Stk+Tail+1);
		if((Now&Mask[i])==Mask[i]&&D==len[i]){
			for(int k=0;k<n;++k)
			    if(f[Now^Mask[i]][k]-k+len[i]==Ans){
			    	Now^=Mask[i],D=k,Ans=f[Now][D],Res.pb(i);
			    	Rt=ans[i].fi,tail1=0,dfs1(ans[i].fi,-1,ans[i].se);
			    	break;
				}
		}
		while(tail&&stk[tail].pos==2*i-1){
			f[stk[tail].mask][stk[tail].lcp]=stk[tail].Preval;
			d[stk[tail].mask][stk[tail].lcp]=stk[tail].lstd;
			--tail;
		}
		while(f[Now][D]<Ans)++D;
	}
	printf("%d\n",Res.size());
	for(int i=1;i<n;++i)printf("%d ",min(pw[i],1));
	puts("");
	for(auto v:Res)printf("%d %d\n",ans[v].fi-1,ans[v].se-1);*/
}
int main(){
	puts("0");
    int T,o;cin>>T>>o;
    while(T--)solve();
	return 0;
}