// 那就是希望。
// 即便需要取模，也是光明。

#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
// Your shadow Gets in the way of my light
uint U[18],V[18],W[18];
std::vector<uint>E[18];
uint End[1u<<18|1],S[1u<<20|1],From[1u<<20|1],To[1u<<20|1],Last[1u<<20|1],cnt;
uint Go[18][18];
voi dfs0(uint p,uint r,uint a,uint b)
{
    if(b)Last[cnt]=End[a],S[cnt]=b,From[cnt]=p,To[cnt]=r,End[a]=cnt++;
    for(auto e:E[p])if(!(b>>e&1))
    {
        if(W[e]!=1)dfs0(U[e]^V[e]^p,r,a<<1,b|1u<<e);
        if(W[e])dfs0(U[e]^V[e]^p,r,a<<1|1,b|1u<<e);
    }
}
uint R[1u<<17|1];
uint Dp[18][1u<<17|1],n;bol Upd[18][1u<<17|1];
uint Q[18][1u<<17|1],Qc[18];
uint Id1[41000005],W1[41000005],tp1;
uint Id2[2500005],W2[2500005],tp2;
voi tryupd(uint d,uint s,uint v)
{
    if(v>Dp[d][s])
    {
        Id1[tp1]=d<<(n-1)|s,W1[tp1]=Dp[d][s],tp1++,Dp[d][s]=v;
        if(d+R[s]<v)Id2[tp2]=s,W2[tp2]=R[s],tp2++,R[s]=v-d;
        if(d&&!Upd[d][s])Upd[d][s]=true,Q[d][Qc[d]++]=s;
    }
}
uint T1[18][1u<<17|1],T2[18][1u<<17|1];
voi dfs(uint d,uint s)
{
    for(uint e=End[s|1u<<d];~e;e=Last[e])
        for(uint t=(1u<<(n-1))-1;~t;t--)t&=~S[e],tryupd(d,S[e]|t,R[t]+d);
    if(d<n-1)dfs(d+1,s),dfs(d+1,s|1u<<d);
    T1[d][s]=tp1,T2[d][s]=tp2;
    while(Qc[d])Qc[d]--,Upd[d][Q[d][Qc[d]]]=false,tryupd(d-1,Q[d][Qc[d]],Dp[d][Q[d][Qc[d]]]);
}
std::vector<uint>Ans;
voi dfs2(uint d,uint s,uint&wil,uint&w)
{
    while(tp1>T1[d][s])tp1--,Dp[Id1[tp1]>>(n-1)][Id1[tp1]&((1u<<(n-1))-1)]=W1[tp1];
    while(tp2>T2[d][s])tp2--,R[Id2[tp2]]=W2[tp2];
    if(d<n-1)dfs2(d+1,s|1u<<d,wil,w),dfs2(d+1,s,wil,w);
    for(uint e=End[s|1u<<d];~e;e=Last[e])if((wil&S[e])==S[e]&&R[wil^S[e]]+d==w)Ans.push_back(e),wil^=S[e],w-=d;
}
voi solve()
{
    scanf("%u",&n);for(uint i=0;i<n;i++)E[i].clear();
    for(uint i=0;i<n-1;i++)scanf("%u%u%u",U+i,V+i,W+i),E[U[i]].push_back(i),E[V[i]].push_back(i);
    for(uint i=0;i<(1u<<n);i++)End[i]=-1;
    cnt=0;for(uint i=0;i<n;i++)dfs0(i,i,1,0);
    for(uint i=0;i<n;i++)for(uint j=0;j<(1u<<(n-1));j++)Dp[i][j]=0;
    for(uint i=0;i<(1u<<(n-1));i++)R[i]=0;
    tp1=tp2=0,dfs(0,0);
    uint s=(1u<<(n-1))-1;uint w=Dp[0][s];printf("%u\n",w+1);Ans.clear(),dfs2(0,0,s,w);if(w)exit(233);
    for(uint i=0;i<n;i++)
    {
        for(uint j=0;j<n;j++)Go[i][j]=-1;
        Go[i][i]=n;std::vector<uint>Q{i};
        while(Q.size())
        {
            uint p=Q.back();Q.pop_back();
            for(auto e:E[p])if(!~Go[i][U[e]^V[e]^p])Q.push_back(U[e]^V[e]^p),Go[i][Q.back()]=e;
        }
    }
    for(auto s:Ans){uint u=From[s],v=To[s],w=S[s];while(u!=v)W[Go[v][u]]=w&1,w>>=1,u^=U[Go[v][u]]^V[Go[v][u]];}
    printf("%u\n",(uint)Ans.size());
    for(uint i=0;i<n;i++)printf("%c%c","10"[!W[i]]," \n"[i==n-1]);
    for(auto s:Ans)printf("%u %u\n",From[s],To[s]);
}
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    freopen("QAQ.out","w",stdout);
#endif
    uint t;scanf("%u%*u",&t),puts("0");
    while(t--)solve();
    return 0;
}

// 那就是希望。
// 即便需要取模，也是光明。