#include<bits/stdc++.h>
using namespace std;
namespace my_std{
	#define ll int
	#define bl bool
	ll my_pow(ll a,ll b,ll mod){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res=(res*a)%mod;
			a=(a*a)%mod;
			b>>=1;
		}
		return res;
	}
	ll qpow(ll a,ll b){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res*=a;
			a*=a;
			b>>=1;
		}
		return res;
	}
	#define db double
	#define pf printf
	#define pc putchar
	#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
	#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
	#define go(u) for(ll i=head[u];i;i=e[i].nxt)
	#define enter pc('\n')
	#define space pc(' ')
	#define fir first
	#define sec second
	#define MP make_pair
	#define il inline
	#define inf 1e9
	#define random(x) rand()*rand()%(x)
	#define inv(a,mod) my_pow((a),(mod-2),(mod))
	il ll read(){
		ll sum=0,f=1;
		char ch=0;
		while(!isdigit(ch)){
			if(ch=='-') f=-1;
			ch=getchar();
		}
		while(isdigit(ch)){
			sum=sum*10+(ch^48);
			ch=getchar();
		}
		return sum*f;
	}
	il void write(ll x){
		if(x<0){
			x=-x;
			pc('-');
		}
		if(x>9) write(x/10);
		pc(x%10+'0');
	}
	il void writeln(ll x){
		write(x);
		enter;
	}
	il void writesp(ll x){
		write(x);
		space;
	}
}
using namespace my_std;
vector<pair<ll,ll> > vec[400040],res;
vector<ll> F[18];
pair<ll,ll> mp[262144];
pair<pair<ll,ll>,ll> st[3000030];
ll t,o,n,head[22],cnt=0,d[22],top=0;
ll rt=1,tot=1,ch[400040][2],f[18][131072],g[131072],lst;
bl ck[18][131072];
struct node{
	ll nxt,to,w,id;
}e[44];
void add(ll u,ll v,ll ww,ll idd){
	e[++cnt].nxt=head[u];
	e[cnt].to=v;
	e[cnt].w=ww;
	e[cnt].id=idd;
	head[u]=cnt;
}
void dfs(ll RT,ll fa,ll u,ll &now,ll S,ll col){
	if(!now) now=++tot;
	if(fa&&(d[RT]==1||d[u]==1)){
		if(RT<u){
			vec[now].push_back(MP(S<<1,col));
			mp[S<<1]=MP(RT,u);
		}
		else{
			vec[now].push_back(MP(S<<1|1,col));
			mp[S<<1|1]=MP(RT,u);
		}
	}
	go(u){
		ll v=e[i].to;
		if(v==fa) continue;
		if(e[i].w!=1) dfs(RT,u,v,ch[now][0],S|(1<<e[i].id),col);
		if(e[i].w) dfs(RT,u,v,ch[now][1],S|(1<<e[i].id),col|(1<<e[i].id));
	}
}
il void chkmax(ll x,ll S){
	if(f[g[S]][S]==-inf||(f[g[S]][S]-g[S])<(f[x][S]-x)) g[S]=x;
}
void solve(ll x,ll dep){
	sort(vec[x].begin(),vec[x].end());
	vec[x].erase(unique(vec[x].begin(),vec[x].end()),vec[x].end());
	fr(i,0,(ll)vec[x].size()-1){
		if(i&&(vec[x][i].fir>>1)==(vec[x][i-1].fir>>1)) continue;
		ll tmp=((1<<(n-1))-1)^((1<<(lst+1))-1);
		fr(j,lst+1,n-1){
			fr(k,0,(ll)F[j].size()-1){
				ll S=F[j][k];
				if(f[lst][S]<f[j][S]){
					f[lst][S]=f[j][S];
					chkmax(lst,S);
					if(!ck[lst][S]){
						ck[lst][S]=1;
						F[lst].push_back(S);
					}
					st[++top]=MP(MP(S<<6|lst,j),0);
				}
				ck[j][S]=0;
			}
			F[j].clear();
		}
		ll u=vec[x][i].fir>>1;
		tmp=u^((1<<(n-1))-1);
		for(ll S=tmp;;S=(S-1)&tmp){
			if(f[g[S]][S]!=-inf&&f[dep][S|u]<(f[g[S]][S]+dep-g[S])){
				f[dep][S|u]=f[g[S]][S]+dep-g[S];
				st[++top]=MP(MP((S|u)<<6|dep,vec[x][i].fir<<6|g[S]),vec[x][i].sec);
				if(!ck[dep][S|u]){
					ck[dep][S|u]=1;
					F[dep].push_back(S|u);
				}
				chkmax(dep,S|u);
			}
			if(!S) break;
		}
		lst=dep;
	}
	if(ch[x][0]) solve(ch[x][0],dep+1);
	if(ch[x][1]) solve(ch[x][1],dep+1);
	lst=min(lst,dep-1);
}
il void clr(){
	fr(i,1,n) head[i]=d[i]=0;
	cnt=0;
	fr(i,1,tot){
		vec[i].clear();
		ch[i][0]=ch[i][1]=0;
	}
	rt=tot=1;
	fr(i,0,n-1) F[i].clear();
	fr(i,0,(1<<(n-1))-1) g[i]=0;
	fr(i,0,n-1) fr(j,0,(1<<(n-1))-1) ck[i][j]=0;
	res.clear();
	top=0;
}
int main(){
	t=read();
	o=read();
	writeln(1);
	while(t--){
		n=read();
		fr(i,2,n){
			ll u=read()+1,v=read()+1,w=read();
			add(u,v,w,i-2);
			add(v,u,w,i-2);
			d[u]++;
			d[v]++;
		}
		fr(i,1,n) dfs(i,0,i,rt,0,0);
		fr(i,0,n-1) fr(j,0,(1<<(n-1))-1) f[i][j]=-inf;
		f[0][0]=0;
		F[0].push_back(0);
		ck[0][0]=1;
		lst=0;
		solve(rt,0);
		ll x=0,y=0,ans=0;
		fr(i,0,n-1){
			fr(S,0,(1<<(n-1))-1){
				if(ans<f[i][S]){
					ans=f[i][S];
					x=S;
					y=i;
				}
			}
		}
		writeln(ans+1);
		ll ncol=0;
		while(top){
			if(st[top].fir.fir==(x<<6|y)){
				ll xx=st[top].fir.sec>>6,yy=st[top].fir.sec&31;
				if(xx){
					ncol|=st[top].sec;
					res.push_back(mp[xx]);
				}
				x^=(xx>>1);
				y=yy;
			}
			top--;
		}
		fr(i,0,n-2) if(e[2*i+1].w==1) ncol|=1<<i;
		writeln((ll)res.size());
		fr(i,0,n-2) writesp((ncol>>i)&1);
		enter;
		fr(i,0,(ll)res.size()-1) pf("%d %d\n",res[i].fir-1,res[i].sec-1);
		clr();
	}
}