#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=18+5,M=(1<<17)+5,K=(1<<26)+5,mod=999911659,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
int n,m,k;
struct edge{int x,id,w;};
vector<edge> S[N];
struct node{
	int S,x,y,cp,le;
}A[M*N];int Ah;
void dfs(int x,int La,int id,int s,int cp){
	if(x^id) A[++Ah]=(node){k^s,x,id,cp,__builtin_popcount(s)};
	for(auto i:S[x]) if(i.x^La) {
		if(i.w) dfs(i.x,x,id,s|(1<<i.id-1),cp|(1<<n-__builtin_popcount(s)));
		if(i.w^1) dfs(i.x,x,id,s|(1<<i.id-1),cp);
	}
}
int f[N][M];
vector<int> T[N];
void Solve(){
	int i,j,h;scanf("%d",&n);for(i=1;i<=n;i++) S[i].clear();Ah=0;
	k=(1<<n-1)-1;
	for(i=1;i<n;i++){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);x++,y++;
		S[x].emplace_back((edge){y,i,z});S[y].emplace_back((edge){x,i,z});
	}
	for(i=1;i<=n;i++) dfs(i,0,i,0,0);
	for(j=0;j<n;j++) for(T[j].clear(),i=0;i<=k;i++) f[j][i]=-INF;
	f[0][0]=1;
	sort(A+1,A+Ah+1,[](node x,node y){return x.cp^y.cp?x.cp<y.cp:x.le<y.le;});
	int cnt=0;
	for(i=1;i<=Ah;i++){
		auto modify=[&i,&cnt](int x,int y,int w){
			if(w>f[x][y]&&w>=0) f[x][y]=w,cnt++;
		};
		int len=A[i].le;
		for(h=0;h<A[i].le;h++) {
			for(j=A[i].S;j;j=(j-1)&A[i].S) modify(n-1,j^k,f[h][A[i].S^j]+len-h);
			modify(n-1,k,f[h][A[i].S]+len-h);
		}
		T[n-1].emplace_back(A[i].S);
		if(i^Ah){
			len=0;while(len<A[i].le&&len<A[i+1].le&&(A[i].cp>>n-len&1)==(A[i+1].cp>>n-len&1)) len++;
			for(j=len+1;j<n;j++) {
				for(int h:T[j]) {
					for(int o=h;o;o=(o-1)&h) modify(len,o^k,f[j][o^k]),f[j][o^k]=-INF;
					modify(len,k,f[j][k]);f[j][k]=-INF;
					T[len].emplace_back(h);
				}
				T[j].clear();
			}
		}
		int mx=0;for(j=0;j<=m;j++) mx=max(mx,f[j][k]);
	}
	int tot=0;for(i=0;i<n;i++) for(j=0;j<=k;j++) tot=max(tot,f[i][j]);
	printf("%d\n",tot);
}
int main(){
	int t,o;
	printf("0\n");
	scanf("%d%d",&t,&o);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}