#include<bits/stdc++.h>
using namespace std;
struct edge{int v,w,id,nxt;}e[40];
struct node{int s,t,len,x,y;}a[2000005];
struct point{int x,y,val;}st[30000005];
int cnt,h[20],tot,T,tp,n,u,v,w,f[(1<<18)+5][20],val[2000005],top,dep[20],anc[20];
int p1[2000005],p2[2000005],col[20],c[20],d[20],pre[20];
void add(int u,int v,int w,int id){e[++cnt]={v,w,id,h[u]};h[u]=cnt;}
void dfs(int u,int fa,int s,int t,int len,int st)
{
	if(len)a[++tot]={s,t,len,st,u};
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa)continue;
		if(e[i].w==0||e[i].w==2)dfs(v,u,s,t|(1<<e[i].id),len+1,st);
		if(e[i].w==1||e[i].w==2)dfs(v,u,s|(1<<len),t|(1<<e[i].id),len+1,st);
	}
}
void dfs1(int u,int fa)
{
	dep[u]=(fa==-1?1:dep[fa]+1);anc[u]=fa;
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa)continue;
		pre[v]=e[i].id;dfs1(v,u);
	}
}
bool operator <(node x,node y)
{
	int p=__builtin_ctz(x.s^y.s);
	if(p<min(x.len,y.len))return ((x.s>>p)&1)<((y.s>>p)&1);
	return x.len<y.len;
}
int query(node x,node y)
{
	int p=__builtin_ctz(x.s^y.s);
	if(p<min(x.len,y.len))return p;
	return min(x.len,y.len);
}
void cmax(int &x,int y){x=(x>y?x:y);}
void cmin(int &x,int y){x=(x<y?x:y);}
void change(int i,int j,int val)
{
	if(f[i][j]==val)return;
	st[++top]={i,j,f[i][j]};f[i][j]=val;
}
void go(int x){while(top>x)f[st[top].x][st[top].y]=st[top].val,top--;}
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin>>T>>tp;cout<<1<<'\n';
    for(int k=1;k<=T;k++)
    {
    	cin>>n;
    	for(int i=0;i<n;i++)h[i]=col[i]=0;cnt=0;tot=0;top=0;
    	for(int i=0;i<n-1;i++)
    	{
    		cin>>u>>v>>w;col[i]=w;
    		add(u,v,w,i);add(v,u,w,i);
		}
		for(int i=0;i<n;i++)dfs(i,-1,0,0,0,i);dfs1(0,-1);
		stable_sort(a+1,a+tot+1);
		for(int i=0;i<(1<<(n-1));i++)for(int j=0;j<n;j++)f[i][j]=!j;
		for(int i=1;i<=tot;i++)val[i]=query(a[i],a[i-1]);
		for(int i=1;i<=tot;i++)
		{
			int lcp=val[i],now=n-1;p1[i]=top;
			for(int x=i-1;x>=0;x--)
			{
				cmin(now,a[x].len);
				if(x!=i-1)cmin(now,val[x+1]);
				if(now<=lcp)break;
				for(int s=a[x].t;s<(1<<(n-1));s=a[x].t|(s+1))
				{
					if(f[s][now]>f[s][lcp])change(s,lcp,f[s][now]);
					change(s,now,0);
				}
			}
			p2[i]=top;
			for(int s=a[i].t;s<(1<<(n-1));s=a[i].t|(s+1))
			{
				int t=s^a[i].t,w=f[s][a[i].len];
				for(int j=0;j<=val[i];j++)cmax(w,f[t][j]+a[i].len-j);
				change(s,a[i].len,w);
			}
		}
		int pos=0,ans=0,s=(1<<(n-1))-1;
		for(int i=0;i<n;i++)if(f[(1<<(n-1))-1][i]>=ans)ans=f[(1<<(n-1))-1][i],pos=i;
		cout<<ans<<'\n';
		vector<int>res;
		for(int i=tot;i>=1;i--)
		{
			go(p2[i]);
			if((s|a[i].t)==s&&pos==a[i].len)
			{
				for(int j=val[i];j>=0;j--)
				{
					if(f[s^a[i].t][j]+a[i].len-j==ans)
					{
						pos=j;ans-=a[i].len-j;
						s^=a[i].t;res.emplace_back(i);
						break;
					}
				}
			}
			go(p1[i]);
			while(ans!=f[s][pos])pos++;
		}
		for(int i=0;i<res.size();i++)
		{
			int u=a[res[i]].x,v=a[res[i]].y,tot1=0,tot2=0;
			while(u!=v)
			{
				if(dep[u]>=dep[v])
				{
					c[++tot1]=pre[u];
					u=anc[u];
				}
				else 
				{
					d[++tot2]=pre[v];
					v=anc[v];
				}
			}
			reverse(d+1,d+tot2+1);
			for(int j=1;j<=tot2;j++)c[++tot1]=d[j];
			for(int j=1;j<=tot1;j++)col[c[j]]=(a[res[i]].s>>(j-1))&1;
		}
		cout<<res.size()<<'\n';
		for(int i=0;i<n-1;i++)cout<<col[i]<<' ';cout<<'\n';
		for(int i=0;i<res.size();i++)cout<<a[res[i]].x<<' '<<a[res[i]].y<<'\n';
	}
	return 0;
}