#include<bits/stdc++.h>
using namespace std;
int n;
int oi[18][18],wc[18];
vector<int>g[18];
#define pb push_back
struct ed{int S,k,u,v;};
vector<ed>st[1<<20];
int rb;
bool of[20][20][1<<18];
void dfs(int x,int f,int S,int u,int k){
	if(f!=-1&&!of[min(x,rb)][max(x,rb)][u])
	of[min(x,rb)][max(x,rb)][u]=1,st[u].pb((ed){S,k,rb,x});
	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,k);
		if(wc[w]!=0)dfs(v,x,S|(1<<w),u<<1|1,k|(1<<w));
	}
}
int js[1<<21],E,le[1<<21],sv[1<<21],lc[1<<21],jt[1<<21],jl[1<<21],jr[1<<21];
void pr(int x,int d){
	if(d==n)return;
	for(ed t:st[x])
		js[++E]=t.S,jt[E]=t.k,le[E]=d,sv[E]=x,jl[E]=t.u,jr[E]=t.v;
	pr(x<<1,d+1),pr(x<<1|1,d+1);
}
const int I=1e9;
short dp[1<<17][20];
vector<int>o[20];
void ad(short &x,short 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;
}
int tx[20100000],ty[20100000],top;
short tz[20100000];int tt[20010000];
int U[20],V[20],cc;
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;i<n;i++)for(int j=0;j<n;j++)for(int s=0;s<(1<<n);s++)
	of[i][j][s]=0;
	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++)rb=i,dfs(i,-1,0,1,0);
	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);
	top=0;
	cc=0;
	for(int i=1;i<=E;i++){
		if(i>1){
			lc[i]=((sv[i]==sv[i-1])?le[i]:jb(sv[i],sv[i-1]));
			for(int j=lc[i]+1;j<=n;j++)if(!o[j].empty()){
				for(int so:o[j]){
					if(dp[so][lc[i]]<dp[so][j]){
						tx[++top]=so,ty[top]=lc[i],tz[top]=dp[so][lc[i]];
						tt[top]=i*2-1;
						if(dp[so][lc[i]]==-1)o[lc[i]].pb(so);
						dp[so][lc[i]]=dp[so][j];
					}
					tx[++top]=so,ty[top]=j,tz[top]=dp[so][j],tt[top]=i;
					tt[top]=i*2-1;
					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]]>=zd)continue;
				if(dp[js[i]|s2][le[i]]<0)o[le[i]].pb(js[i]|s2);
				tx[++top]=js[i]|s2,ty[top]=le[i],tz[top]=dp[js[i]|s2][le[i]];
				dp[js[i]|s2][le[i]]=zd;
				tt[top]=i*2;
			}
			if(!s2)break;s2=(s2-1)&S;
		}
	}
	int as=-1,ai=-1;
	short ans=-1;
	for(int s=0;s<(1<<n);s++)for(int i=0;i<=n;i++)if(ans<dp[s][i])
	ans=dp[s][i],as=s,ai=i;
	for(int i=E;i;i--){
		short fk=dp[as][ai];
		while(top&&tt[top]==i*2)dp[tx[top]][ty[top]]=tz[top],top--;
		bool fl=0;
		if(((as&js[i])==js[i])&&fk>dp[as][ai]){
			for(int o=0;o<=n;o++)if(dp[as^js[i]][o]+le[i]-o==fk){
				as^=js[i],ai=o;
				fl=1;break;
			}
		}
		if(fl){
			for(int j=0;j<n;j++)
			if((js[i]>>j)&1)wc[j]=((jt[i]>>j)&1);
			U[++cc]=jl[i],V[cc]=jr[i];
		}
		fk=dp[as][ai];
		while(top&&tt[top]==i*2-1)dp[tx[top]][ty[top]]=tz[top],top--;
		if(i==1)continue;
		if(ai<lc[i])continue;
		for(int j=lc[i];j<=n;j++)if(dp[as][j]==fk){ai=j;break;}
	}
	printf("%d\n",(int)ans+1);
	printf("%d\n",cc);
	for(int i=0;i<n;i++){
		if(wc[i]==2)wc[i]=0;
		printf("%d ",wc[i]);
	}
	puts("");
	for(int i=1;i<=cc;i++)printf("%d %d\n",U[i],V[i]);
}
int main(){
	int T,tt;
	puts("1");
	scanf("%d%d",&T,&tt);while(T--)sol();
	return 0;
}