#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> void chkmin(T& x, T y) { x = min(x, y); }
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
const int N = 20;
int _, o, n, height[2 * N * (1 << 18)], f[N][1 << 17], val[N];
vector <pair <int, int>> v[N], path;
vector <int> edge[N][N];
vector <array <int, 4>> g[N][1 << 17];
vector <pair <string, pair <int, pair <int, int>>>> tt;
void dfs(int rt, int x, int fa, int num, string st) {
	if (num) tt.emplace_back(st, make_pair(num, make_pair(rt, x)));
	for (auto i: v[x])
		if (i.first != fa) {
			if (val[i.second] != 1) dfs(rt, i.first, x, num | (1 << (i.second - 1)), st + "0");
			if (val[i.second] != 0) dfs(rt, i.first, x, num | (1 << (i.second - 1)), st + "1");
		}
}
void dfs2(int rt, int x, int fa) {
	for (auto i: v[x])
		if (i.first != fa) {
			edge[rt][i.first] = edge[rt][x];
			edge[rt][i.first].push_back(i.second);
			dfs2(rt, i.first, x);
		}
}
void cmax(int id, int a, int b, int c, int d, int v) {
	if (f[c][d] + v > f[a][b]) {
		f[a][b] = f[c][d] + v;
		g[a][b].emplace_back(array <int, 4> {id, c, d, v});
	}
}
void work(int pos, int x, int y) {
	while (g[x][y].size() && g[x][y].back()[0] > pos) g[x][y].pop_back();
	if (g[x][y].empty()) return;
	// cout << "# " << x << " " << y << " " << g[x][y].back()[0] << " " << g[x][y].back()[1] << " " << g[x][y].back()[2] << " " << g[x][y].back()[3] << endl;
	if (g[x][y].back()[3]) {
		// puts("!");
		path.emplace_back(tt[g[x][y].back()[0]].second.second.first, tt[g[x][y].back()[0]].second.second.second);
		int z = 0;
		for (int i: edge[tt[g[x][y].back()[0]].second.second.first][tt[g[x][y].back()[0]].second.second.second]) val[i] = tt[g[x][y].back()[0]].first[z++] - '0';
	} work(g[x][y].back()[0] - 1, g[x][y].back()[1], g[x][y].back()[2]);
}
void work() {
	path.clear();
	read(n);
	ms(f, 0);
	F(i, 1, n) v[i].clear();
	F(i, 1, n)
		F(j, 1, n)
			edge[i][j].clear();
	tt.clear();
	F(i, 1, n - 1) {
		int x, y; read(x), read(y), read(val[i]);
		x++, y++;
		v[x].emplace_back(y, i);
		v[y].emplace_back(x, i);
	}
	F(i, 1, n) dfs(i, i, 0, 0, ""), dfs2(i, i, 0);
	sort(all(tt));
	// cout << n << " " << tt.size() << " " << N * N * 2 << endl;
	// F(i, 0, SZ(tt)) cout << tt[i].first << " " << tt[i].second << endl;
	F(i, 0, SZ(tt) - 1) {
		int k = 0;
		while (k < tt[i + 1].first.size() && k < tt[i].first.size() && tt[i + 1].first[k] == tt[i].first[k]) k++;
		height[i] = k;
		// cout << "! " << i << " " << height[i] << endl;
	} height[SZ(tt)] = 0;
	int full = (1 << (n - 1)) - 1;
	F(i, 0, n)
		F(j, 0, full)
			g[i][j].clear();
	F(i, 0, SZ(tt)) {
		DF(j, height[i], 0) {
			int k = full ^ tt[i].second.first;
			for (int t = k; ; t = (t - 1) & k) {
				cmax(i, height[i], t | tt[i].second.first, j, t, (int) tt[i].first.size() - j);
				if (t == 0) break;
			}
		}
		int lst = i - 1;
		while ((~lst) && height[lst] > height[i]) {
			int k = tt[lst].second.first;
			for (int j = k; ; j = (j + 1) | k) {
				cmax(i, height[i], j, height[lst], j, 0);
				if (!(j & tt[i].second.first)) cmax(i, height[i], j | tt[i].second.first, height[lst], j, (int) tt[i].first.size() - height[lst]);
				// f[height[lst]][j] = 1e9;
				if (j == full) break;
			}
			lst--;
		}
	}
	int ans = 0, ii = -1, jj = -1;
	F(i, 0, n)
		F(j, 0, full)
			if (f[i][j] > ans) {
				ans = f[i][j];
				ii = i, jj = j;
			}
	cout << ans + 1 << '\n';
	work(SZ(tt), ii, jj);
	cout << path.size() << '\n';
	F(i, 1, n - 1) cout << min(1, val[i]) << " "; cout << '\n';
	for (auto i: path) cout << i.first - 1 << " " << i.second - 1 << '\n';
}
signed main() {
	// freopen("axiumcrisis.in", "r", stdin);
	// freopen("axiumcrisis.out", "w", stdout);
	read(_), read(o);
	while (_--) work();
	return 0;
}