#include <cstdio>
#include <vector>
using namespace std;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=x*10+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
const int N=20,T=2000003,K=10000003,S=1<<17;
typedef pair<int,int> pii;
int n,rt,MskLim;
int hd[N],ver[N<<1],nxt[N<<1],val[N<<1],tot;
void add(int u,int v,int w){
	nxt[++tot]=hd[u];hd[u]=tot;ver[tot]=v;val[tot]=w;
}
int tr[T][2],tnum;
int w[N];
struct path{
	int u,v,msk;
	path(int U,int V,int Msk):u(U),v(V),msk(Msk){}
};
vector<path> vec[T];
void dfs(int u,int fa,int msk,int p){
	if(fa) vec[p].emplace_back(rt,u,msk);
	for(int i=hd[u];i;i=nxt[i]){
		int v=ver[i];
		if(v==fa) continue;
		int id=(i-1)>>1;
		if(val[i]!=1){
			if(!tr[p][0]) tr[p][0]=++tnum;
			dfs(v,u,msk|(1<<id),tr[p][0]);
		}
		if(val[i]!=0){
			if(!tr[p][1]) tr[p][1]=++tnum;
			dfs(v,u,msk|(1<<id),tr[p][1]);
		}
	}
}
int f[S][N],g[S],tg[S];
int fx[K],fy[K],fv[K],fc;
int gx[K],gt[K],gv[K],gc;
inline void upd(int x,int y,int v){
	if(f[x][y]<v){
		++fc;fx[fc]=x;fy[fc]=y;fv[fc]=f[x][y];
		f[x][y]=v;
		if(g[x]<v-y){
			++gc;gx[gc]=x;gt[gc]=tg[x];gv[gc]=g[x];
			g[x]=v-y;tg[x]=y;
		}
	}
}
bool vis[N][S];
int lis[N][S],len[N];
int fA[T],gA[T],fB[T],gB[T];
void trav(int p,int d){
	if(!p) return;
	fA[p]=fc;gA[p]=gc;
	for(auto [u,v,msk]:vec[p])
		for(int i=msk;i<MskLim;i=(i+1)|msk){
			if(!vis[d][i]) vis[d][i]=1,lis[d][len[d]++]=i;
			upd(i,d,g[i^msk]+d);
		}
	trav(tr[p][0],d+1);
	trav(tr[p][1],d+1);
	fB[p]=fc;gB[p]=gc;
	if(d){
		for(int it=0;it<len[d];++it){
			int x=lis[d][it];
			upd(x,d-1,f[x][d]);
			if(!vis[d-1][x]) vis[d-1][x]=1,lis[d-1][len[d-1]++]=x;
			vis[d][x]=0;
		}
		len[d]=0;
	}
}
void rollback(int fl,int gl){
	while(fc>fl) f[fx[fc]][fy[fc]]=fv[fc],--fc;
	while(gc>gl) tg[gx[gc]]=gt[gc],g[gx[gc]]=gv[gc],--gc;
}
int tx,ty;
int arr[N],sz,tsz;
int eu[N],ev[N],m;
bool paint(int u,int fa,int goal){
	if(u==goal) return 1;
	for(int i=hd[u];i;i=nxt[i]){
		int v=ver[i];
		if(v==fa) continue;
		if(paint(v,u,goal)){
			w[(i+1)>>1]=arr[tsz--];
			return 1;
		}
	}
	return 0;
}
void recall(int p,int d){
	if(!p) return;
	int las=f[tx][ty];
	rollback(fB[p],gB[p]);
	if(ty==d-1&&f[tx][ty]<las) ++ty;
	arr[++sz]=1;recall(tr[p][1],d+1);--sz;
	arr[++sz]=0;recall(tr[p][0],d+1);--sz;
	las=f[tx][ty];
	rollback(fA[p],gA[p]);
	if(ty==d){
		for(auto [u,v,msk]:vec[p])
			if((tx&msk)==msk&&g[tx^msk]+d==las){
				ty=tg[tx^=msk];
				++m;eu[m]=u;ev[m]=v;
				tsz=sz;paint(u,0,v);
				break;
			}
	}
}
void solve(){
	n=read();tnum=1;MskLim=1<<(n-1);m=0;
	for(int i=1;i<n;++i){
		int u=read()+1,v=read()+1;w[i]=read();
		add(u,v,w[i]);add(v,u,w[i]);
	}
	for(rt=1;rt<=n;++rt) dfs(rt,0,0,1);
	for(int s=0;s<MskLim;++s){
		for(int i=0;i<n;++i) f[s][i]=!i;
		g[s]=1;tg[s]=0;
	}
	trav(1,0);
	tx=MskLim-1;ty=0;
	printf("%d\n",f[MskLim-1][0]);
	for(int it=0;it<len[0];++it) vis[0][lis[0][it]]=0;
	len[0]=0;
	recall(1,0);
	printf("%d\n",m);
	for(int i=1;i<n;++i){
		if(w[i]==2) w[i]=1;
		printf("%d ",w[i]);
	}
	putchar('\n');
	for(int i=1;i<=m;++i) printf("%d %d\n",eu[i]-1,ev[i]-1);
	for(int i=1;i<=n;++i) hd[i]=0;
	while(tot) ver[tot]=nxt[tot]=val[tot]=0,--tot;
	for(int i=1;i<=tnum;++i) tr[i][0]=tr[i][1]=0,vec[i].clear();
}
int main(){
	puts("1");
	int tc=read();read();
	while(tc--) solve();
	return 0;
}