#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
int n,cnt,tot;
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],di[10000003],cnk,a[35],b[35];
pair<int,int> od[10000003],nw[10000003],an[35];
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);
		a[i]=++u,b[i]=++v;
		E[u][v]=E[v][u]=w;
		id[u][v]=id[v][u]=i;
	}
	cnt=tot=cnk=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]){
				if(f[j][up[j]-1]<f[j][up[j]]){
					f[j][up[j]-1]=f[j][up[j]];
					di[++tot]=-1;
					od[tot]=mp(j,up[j]);
					nw[tot]=mp(j,up[j]-1);
				}
				f[j][up[j]]=-1e9;
				up[j]--;
			}
			if((j&s)==0){
				for(int k=0;k<=lcp[i];k++){
					if(f[j+s][len]<f[j][k]+len-k){
						f[j+s][len]=f[j][k]+len-k;
						di[++tot]=i;
						od[tot]=mp(j,k);
						nw[tot]=mp(j+s,len);
					}
				}
				up[j+s]=max(up[j+s],len);
			}
		}
		if(f[s][len]<len){
			f[s][len]=len;
			di[++tot]=i;
			od[tot]=mp(0,0);
			nw[tot]=mp(s,len);
		}
		up[s]=max(up[s],len);
	}
	int ans=0,x=0,y=0;
	for(int j=1;j<lim;j++)
		for(int k=0;k<n;k++)
			if(ans<f[j][k]) ans=f[j][k],x=j,y=k;
	for(int i=tot;i>=1&&x!=0;i--){
		if(nw[i].first==x&&nw[i].second==y){
			if(di[i]!=-1){
				node pp=path[di[i]];
				for(int j=1;j<=pp.len;j++)
					E[pp.road[j]][pp.road[j-1]]=E[pp.road[j-1]][pp.road[j]]=((pp.num/(1<<(n-j)))&1);
				an[++cnk]=mp(pp.st,pp.ed);
			}
			x=od[i].first,y=od[i].second;
		}
	}
	printf("%d\n%d\n",ans+1,cnk);
	for(int i=1;i<n;i++) printf("%d ",E[a[i]][b[i]]%2);
	printf("\n");
	for(int i=1;i<=cnk;i++) printf("%d %d\n",an[i].first-1,an[i].second-1);
}
int main(){
	int t,o;
	scanf("%d%d",&t,&o);
	printf("1\n");
	while(t--) solve();
}