#include<bits/stdc++.h>
using namespace std;
const int M=1.2e7+5;
typedef unsigned char uc;
int T,o,n,u[18],v[18],w[18],ca,tp;
vector<int>e[18];
struct node{
	int W,S,x,y;
}a[M];
int d[M],h[M],T1[M],T2[M];
int p[M<<1];
uc dp[18][1<<17],va[M<<1],fr[18][18],dis[18][18];
bool cmp(node a,node b){
	return a.W==b.W?dis[a.x][a.y]<dis[b.x][b.y]:a.W<b.W;
}
void dfs(int x,int y,int S,int W){
	if(S)a[ca++]={W,S,y,x};
	for(auto z:e[x])if(!(S>>z&1)){
		int t=u[z]^v[z]^x;
		dis[y][t]=dis[y][x]+1,fr[y][t]=z;
		if(w[z]<2)dfs(t,y,S|1<<z,W|w[z]<<(n-1-dis[y][t]));
		else dfs(t,y,S|1<<z,W),dfs(t,y,S|1<<z,W|1<<(n-1-dis[y][t]));
	}
}
inline void chg(int i,int j,int k){
	if(dp[i][j]!=k){
		p[tp]=(i<<n-1)|j,va[tp]=dp[i][j];
		dp[i][j]=k,++tp;
	}
}
inline void revoke(int t){
	while(tp>t)--tp,dp[p[tp]>>n-1][p[tp]&((1<<n-1)-1)]=va[tp];
}
void solve(){
	scanf("%d",&n),ca=0;
	for(int i=0;i<n;++i)e[i].clear();
	for(int i=0;i<n-1;++i){
		scanf("%d%d%d",&u[i],&v[i],&w[i]);
		e[u[i]].push_back(i);
		e[v[i]].push_back(i);
	}
	for(int i=0;i<n;++i)fr[i][i]=-1,dfs(i,i,0,0);
	sort(a,a+ca,cmp);
	for(int i=0;i<ca;++i)d[i]=dis[a[i].x][a[i].y];
	for(int i=1;i<ca;++i){
		h[i]=min(d[i],d[i-1]);
		if(a[i].W!=a[i-1].W)h[i]=min(h[i],n-(33-__builtin_clz(a[i-1].W^a[i].W)));
	}
	for(int i=0;i<n;++i)for(int j=0;j<1<<n-1;++j)dp[i][j]=!i;
	for(int i=0;i<ca;++i){
		T1[i]=tp;
		for(int j=i-1,D=d[j];~j&&D>h[i];D=min(D,h[j--])){
			for(int k=a[j].S;k<1<<n-1;k=(k+1)|a[j].S)if(dp[D][k]){
				if(dp[D][k]>dp[h[i]][k])chg(h[i],k,dp[D][k]);
				chg(D,k,0);
			}
		}
		T2[i]=tp;
		for(int k=a[i].S;k<1<<n-1;k=(k+1)|a[i].S){
			int w=dp[d[i]][k];
			for(int D=h[i];~D;--D)w=max(w,dp[D][k^a[i].S]+d[i]-D);
			chg(d[i],k,w);
		}
	}
	int D=0,ans=0,S=(1<<n-1)-1;
	for(int i=0;i<=d[ca-1];++i)if(dp[i][(1<<n-1)-1]>ans)ans=dp[i][(1<<n-1)-1],D=i;
	printf("%d\n",ans);
	vector<int>tmp;
	for(int i=ca-1;~i;--i){
		revoke(T2[i]);
		if((S|a[i].S)==S&&D==d[i]){
			for(int j=h[i];~j;--j)if(dp[j][S^a[i].S]+d[i]-j==ans){
				D=j,S^=a[i].S,ans-=d[i]-j;
				tmp.push_back(i);
				break;
			}
		}
		revoke(T1[i]);
		while(dp[D][S]!=ans)++D;
	}
	for(auto z:tmp){
		int x=a[z].x,y=a[z].y;
		while(~fr[x][y]){
			w[fr[x][y]]=a[z].W>>(n-1-dis[x][y])&1;
			y^=u[fr[x][y]]^v[fr[x][y]];
		}
	}
	printf("%d\n",tmp.size());
	for(int i=0;i<n-1;++i)printf("%d%c",w[i]," \n"[i==n-2]);
	for(auto z:tmp)printf("%d %d\n",a[z].x,a[z].y);
}
int main(){
	scanf("%d%d",&T,&o);
	puts("1");
	while(T--)solve();
	return 0;
}