#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>

using std::min;
const int N = 18 * 18 * 18 + 5, INF = 100000000;
struct Edge {int to, id, nxt, w;} e[37];
int LCP(bool *a, bool *b, int la, int lb) {
    for (int i = 1; i <= min(la, lb); ++ i) if (a[i] != b[i]) return i - 1;
    return min(la, lb);
}
struct node {
    bool str[19]; int len, S, u, v;
    inline bool operator < (const node &rhs) const {
        for (int i = 1; i <= min(len, rhs.len); ++ i)
            if (str[i] < rhs.str[i]) return true;
            else if (str[i] > rhs.str[i]) return false;
        return len < rhs.len;
    }
} a[N];
int head[19], sta[19], f[19][1 << 17 | 1], lst[19][1 << 17 | 1], top, tot, m, nows;
int nf[19][1 << 17 | 1], nlst[19][1 << 17 | 1];
inline void ae(int u, int v, int w, int id) {
    e[++ tot].to = v, e[tot].w = w, e[tot].id = id, e[tot].nxt = head[u], head[u] = tot;
}
int rtnow;
//
void dfs(int u, int fa) {
    if (top) {
        int pre = min(top, 3);
        for (int S = 0; S < 1 << pre; ++ S) {
            bool flg = true; ++ m;
            for (int i = 1; i <= pre; ++ i) {
                if (sta[i] != 2 && (S >> i - 1 & 1) != sta[i]) {flg = false; break;}
                a[m].str[i] = S >> i - 1 & 1;
            }
            if (!flg) {-- m; continue;}
            for (int i = pre + 1; i <= top; ++ i) a[m].str[i] = (sta[i] == 1);
            assert(top);
            a[m].len = top, a[m].S = nows, a[m].u = rtnow, a[m].v = u;
        }
    }
    for (int i = head[u]; i; i = e[i].nxt) if (e[i].to != fa) {
        int v = e[i].to; sta[++ top] = e[i].w, nows |= 1 << e[i].id;
        dfs(v, u), -- top, nows ^= 1 << e[i].id;
    }
}
int stk[50000005], pre[50000005], b[N], w[19], pthu[19], pthv[19], eg[19], cur;
bool find(int u, int tar, int fa) {
    if (u == tar) return true;
    bool flg = false;
    for (int i = head[u]; i; i = e[i].nxt) if (e[i].to != fa) {
        eg[++ cur] = e[i].id; bool tmp = find(e[i].to, tar, u);
        if (tmp) {flg = true; break;}
        else -- cur;
    }
    return flg;
}

int main() {
    freopen("bridge.in", "r", stdin);
    puts("1"); int _; scanf("%d%*d", &_);
    while (_ --) {
        memset(head, 0, sizeof head), tot = m = top = 0;
        int n; scanf("%d", &n);
        for (int i = 0, u, v, w; i < n - 1; ++ i)
            scanf("%d%d%d", &u, &v, &w), ++ u, ++ v, ae(u, v, w, i), ae(v, u, w, i);
        for (int i = 1; i <= n; ++ i) rtnow = i, dfs(i, -1);
        std::sort(a + 1, a + m + 1);
        top = 0, b[0] = b[m] = 0;
        for (int i = 1; i < m; ++ i)
            b[i] = LCP(a[i].str, a[i + 1].str, a[i].len, a[i + 1].len);
        for (int j = 0; j <= n; ++ j)
        for (int S = 0; S < 1 << n - 1; ++ S) f[j][S] = -INF, lst[j][S] = 0;
        f[0][0] = 0;
        for (int i = 1; i <= m; ++ i) {
            for (int j = 0; j <= b[i]; ++ j)
            for (int S = 0; S < 1 << n - 1; ++ S) nf[j][S] = -INF, nlst[j][S] = 0;
            for (int j = 0; j <= b[i - 1]; ++ j)
            for (int S = 0; S < 1 << n - 1; ++ S) if (f[j][S] >= 0) {
                int t = min(b[i], j);
                if (nf[t][S] < f[j][S]) nf[t][S] = f[j][S], nlst[t][S] = lst[j][S];
                if (!(S & a[i].S)) {
                    int S0 = S | a[i].S;
                    if (nf[b[i]][S0] < f[j][S] + a[i].len - j) {
                        nf[b[i]][S0] = f[j][S] + a[i].len - j;
                        nlst[b[i]][S0] = ++ top, stk[top] = i;
                        pre[top] = lst[j][S];
                    }
                }
            }
            for (int j = 0; j <= b[i]; ++ j)
            for (int S = 0; S < 1 << n - 1; ++ S)
                f[j][S] = nf[j][S], lst[j][S] = nlst[j][S];
        }
        int ans = 0, mxi = 0, mxj = 0;
        for (int i = 0; i <= n; ++ i)
        for (int S = 0; S < 1 << n - 1; ++ S)
            if (f[i][S] > ans) ans = f[mxi = i][mxj = S];
        int now = lst[mxi][mxj], len = 0;
        while (now) {
            int i = stk[now];
            cur = 0, find(a[i].u, a[i].v, -1);
            for (int j = 1; j <= cur; ++ j) w[eg[j]] = a[i].str[j];
            pthu[++ len] = a[i].u, pthv[len] = a[i].v;
            now = pre[now];
        }
        printf("%d\n%d\n", ans + 1, len);
        for (int i = 1; i < n; ++ i) printf("%d ", w[i]);
        puts("");
        for (int i = 1; i <= len; ++ i) printf("%d %d\n", pthu[i] - 1, pthv[i] - 1);
    }
    return 0;
}