#include <bits/stdc++.h>
using namespace std;
#define For(Ti,Ta,Tb) for(auto Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(auto Ti=(Ta);Ti>=(Tb);--Ti)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
using ll=long long;
mt19937 eng(random_device{}());
const int N=19;
int T,tid,n,a[N],val[N],vis[N];
vector<pair<int,int>> e[N];
struct Trie{
	int ch[N][2],tot;
}trie;
struct Answer{
	int tot;
	vector<int> val;
	vector<pair<int,int>> path;
}ans,cur;
void dfs(int,bool);
bool flg;
void get_path(int8_t u,int8_t v,int8_t fa,int8_t v_,bool ok,bool fir_){
	if(fa&&e[v].size()==1&&ok){
		cur.path.emplace_back(u,v);
		int pre=cur.tot;
		cur.tot=trie.tot;
		dfs(n>11?u+1:u,fir_);
		cur.tot=pre;
		cur.path.pop_back();
	}
	for(auto [x,i]:e[v]){
		if(x!=fa&&!vis[i]){
			vis[i]=1;
			int dst=eng()%2;
			For(y,0,1){
				if((val[i]!=2&&y!=val[i])||(val[i]==2&&!fir_&&y!=dst)){
					continue;
				}
				int pre=val[i];
				val[i]=y;
				int& nxt=trie.ch[v_][val[i]],ok_=0;
				if(!nxt){
					nxt=++trie.tot;
					ok_=1;
				}
				get_path(u,x,v,nxt,ok_,fir_&&(pre!=2||(n<=11&&!flg)));
				if(ok_){
					nxt=0;
					--trie.tot;
				}
				val[i]=pre;
			}
			vis[i]=0;
		}
	}
}
void dfs(int u,bool fir){
	if(u==n+1){
		if(cur.tot>ans.tot){
			cur.val.resize(n-1);
			For(i,0,n-2){
				cur.val[i]=val[i+1]!=2?val[i+1]:0;
			}
			ans=cur;
		}
		return;
	}
	if(count(vis+1,vis+n,0)+cur.tot<=ans.tot){
		return;
	}
	Trie pret=trie;
	dfs(u+1,fir);
	trie=pret;
	get_path(u,u,0,0,0,fir);
}
namespace zero{
	void dfs(int u,int fa,int d,int& x,int& xd){
		if(d>xd){
			x=u;
			xd=d;
		}
		for(auto [v,i]:e[u]){
			if(v!=fa){
				dfs(v,u,d+1,x,xd);
			}
		}
	}
	tuple<int,int,int> diam(){
		int x=0,xd=-1,y=0,yd=-1;
		dfs(1,0,0,x,xd);
		dfs(x,0,0,y,yd);
		return {x,y,yd};
	}
	void solve(){
		auto [u,v,d]=diam();
		cout<<d+1<<'\n';
		cout<<"1\n";
		For(i,1,n-1) cout<<0<<" \n"[i==n-1];
		cout<<u-1<<' '<<v-1<<'\n';
		For(i,1,n) e[i].clear();
	}
}
int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	// assert(freopen("B.in","r",stdin));
	// assert(freopen("B.out","w",stdout));
	cin>>T>>tid;
	cout<<"1\n";
	while(T--){
		cin>>n;
		For(i,1,n-1){
			int u,v;
			cin>>u>>v>>val[i];
			++u;
			++v;
			e[u].emplace_back(v,i);
			e[v].emplace_back(u,i);
		}
		if(count(val+1,val+n,0)==n-1){
			zero::solve();
			continue;
		}
		flg=count(val+1,val+n,2)==n-1;
		For(i,0,flg||n<=11?0:3) dfs(1,1);
		cout<<ans.tot+1<<'\n';
		cout<<ans.path.size()<<'\n';
		for(int x:ans.val){
			cout<<x<<' ';
		}
		cout<<'\n';
		for(auto [u,v]:ans.path){
			cout<<u-1<<' '<<v-1<<'\n';
		}
		ans.tot=0;
		For(i,1,n) e[i].clear();
	}
	return 0;
}