#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 18
#define M 1048518
using namespace std;
const int inf=(int)(1e9);
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
struct reads
{
	int num,data,snum;
};
struct rds
{
	int x,y,d,st,st2;
};
rds tong[M+1];
struct dst
{
	int num,data;
};
inline dst max(dst a,dst b)
{
	return a.data>b.data?a:b;
}
struct node
{
	int num;
	dst data;
};
node v[1<<N][N+1];
struct path
{
	int x,y;
};
path rd[N+1];
int T,o,sx,sy,n,length,cater,len[1<<N],cl[N+1],fa[N+1],st[N+1],leng,lg[M+1],h[M+1],ST[M+1][21],ans;
dst maxn[1<<N];
vector<reads>E[N+1];
vector<rds>p[N+1][1<<N];
vector<dst>pv[M+1];
bool used[N+1];
void add(int x,int y,int z,int w)
{
	E[x].push_back((reads){y,z,w}),E[y].push_back((reads){x,z,w});
	return;
}
void dfs(int x)
{
	used[x]=1;
	for (int i=0;i<E[x].size();++i)
		if (!used[E[x][i].num])
			fa[E[x][i].num]=x,dfs(E[x][i].num);
	return;
}
void dfs2(int rt,int x,int d,int st,int st2)
{
	if (d) ans=max(ans,d),p[d][st2].push_back((rds){rt,x,d,st,st2});
	for (int i=0;i<E[x].size();++i)
		if (fa[E[x][i].num]==x)
		{
			if (E[x][i].data!=1) dfs2(rt,E[x][i].num,d+1,st|(1<<(E[x][i].snum-1)),st2);
			if (E[x][i].data!=0) dfs2(rt,E[x][i].num,d+1,st|(1<<(E[x][i].snum-1)),st2|(1<<d));
		}
	return;
}
void dfs3(int d,int st)
{
	if (d)
	{
		for (int i=0;i<p[d][st].size();++i) tong[++length]=p[d][st][i];
	}
	if (d!=n-1) dfs3(d+1,st),dfs3(d+1,st|(1<<d));
	return;
}
int lcp(rds a,rds b)
{
	for (int i=0;i<min(a.d,b.d);++i)
		if (((a.st2>>i)&1)!=((b.st2>>i)&1))
			return i;
	return min(a.d,b.d);
}
int query(int x,int y)
{
	if (x>y) swap(x,y);
	x++;
	int lw=lg[y-x+1];
	return min(ST[x][lw],ST[y-(1<<lw)+1][lw]);
}
dst calc(int x,int d)
{
	dst res=(dst){-inf,-inf};
	int wst;
	if (len[x])
	{
		wst=query(v[x][len[x]].data.num,d);
		while (len[x]&&v[x][len[x]].num>=wst) res=max(res,v[x][len[x]].data),len[x]--;
		if (res.data!=-inf) v[x][++len[x]]=(node){wst,res},maxn[x]=max(maxn[x],(dst){res.num,res.data-wst});
	}
	return maxn[x];
}
void insert(int x,int d,int ds)
{
	dst res=(dst){-inf,-inf};
	int wst;
	if (len[x])
	{
		wst=query(v[x][len[x]].data.num,d);
		while (len[x]&&v[x][len[x]].num>=wst) res=max(res,v[x][len[x]].data),len[x]--;
		if (res.data!=-inf) v[x][++len[x]]=(node){wst,res},maxn[x]=max(maxn[x],(dst){res.num,res.data-wst});
	}
	v[x][++len[x]]=(node){inf,(dst){d,ds}};
	return;
}
void adder(int x,int d1,int d2)
{
	dst ds=calc(d1,x);
	pv[x].push_back((dst){d2,ds.num});
	if (ds.data!=-inf&&ds.data+tong[x].d+n-1-__builtin_popcount(d2)>ans)
	{
		insert(d2,x,ds.data+tong[x].d);
		if (ds.data+tong[x].d>ans) ans=ds.data+tong[x].d,sx=x,sy=d2;
	}
	return;
}
int get_pv(int x,int d)
{
	for (int i=0;i<pv[x].size();++i)
		if (pv[x][i].num==d)
			return pv[x][i].data;
	return -1;
}
void get_path(int x,int y,int d)
{
	for (int i=1;i<=n;++i) used[i]=fa[i]=0;
	rd[++cater]=(path){x,y},dfs(x),leng=0;
	while (y) st[++leng]=y,y=fa[y];
	reverse(st+1,st+leng+1);
	for (int i=1;i<=leng-1;++i)
		for (int j=0;j<E[st[i]].size();++j)
			if (E[st[i]][j].num==st[i+1])
				cl[E[st[i]][j].snum]=(d>>(i-1))&1;
	return;
}
int main()
{
	int x,y,z,d;
	for (int i=2;i<=M;++i) lg[i]=lg[i>>1]+1;
	T=read(),o=read(),puts("1");
	for (int qt=1;qt<=T;++qt)
	{
		n=read(),length=ans=sx=sy=cater=0;
		for (int i=1;i<=n;++i) E[i].clear();
		for (int i=0;i<(1<<(n-1));++i) len[i]=0,maxn[i]=(dst){-inf,-inf};
		for (int i=1;i<=n-1;++i)
			for (int j=0;j<(1<<i);++j)
				p[i][j].clear();
		for (int i=1;i<=n-1;++i)
		{
			x=read()+1,y=read()+1,z=read(),add(x,y,z,i);
			if (z!=2) cl[i]=z;
			else cl[i]=0;
		}
		for (int i=1;i<=n;++i)
		{
			for (int j=1;j<=n;++j) used[j]=fa[j]=0;
			dfs(i),dfs2(i,i,0,0,0);
		}
		dfs3(0,0),h[1]=0;
		for (int i=2;i<=length;++i) h[i]=lcp(tong[i-1],tong[i]);
		for (int i=1;i<=length;++i) ST[i][0]=h[i];
		for (int i=1;i<=lg[length];++i)
			for (int j=1;j+(1<<i)-1<=length;++j)
				ST[j][i]=min(ST[j][i-1],ST[j+(1<<(i-1))][i-1]);
		for (int i=1;i<=length;++i) pv[i].clear();
		insert(0,0,0);
		for (int i=1;i<=length;++i)
		{
			d=((1<<(n-1))-1)^tong[i].st;
			for (int j=d;j>0;j=(j-1)&d) adder(i,j,j|tong[i].st);
			adder(i,0,tong[i].st);
		}
		while (sx) d=get_pv(sx,sy),get_path(tong[sx].x,tong[sx].y,tong[sx].st2),sy^=tong[sx].st,sx=d;
		printf("%d\n%d\n",ans+1,cater);
		for (int i=1;i<=n-1;++i) printf("%d ",cl[i]);
		puts("");
		for (int i=1;i<=cater;++i) printf("%d %d\n",rd[i].x-1,rd[i].y-1);
	}
	return 0;
}