#include<cstdio>#include<cstring>#include<cstdlib>#include<cmath>#include<algorithm>#include<string>#include<map>#include<set>#include<iostream>#include<vector>#include<queue>using namespace std;#define sz(v) ((int)(v).size())#define rep(i, n) for (int i = 0; i < (n); ++i)#define repf(i, a, b) for (int i = (a); i <= (b); ++i)#define repd(i, a, b) for (int i = (a); i >= (b); --i)#define clr(x) memset(x,0,sizeof(x))#define clrs( x , y ) memset(x,y,sizeof(x))#define out(x) printf(#x" %dn", x)#define sqr(x) ((x) * (x))typedef long long lint;const int maxint = -1u>>3;const double eps = 1e-8;const int maxn = 400 + 10;int sgn(const double &x) { return (x > eps) - (x < -eps); }struct Graph { int w[maxn][maxn], lx[maxn], ly[maxn], matx[maxn], maty[maxn], slk[maxn], n; bool fx[maxn], fy[maxn]; void get_max(int &x, int y) { x = max(x, y); } void get_min(int &x, int y) { x = min(x, y); } void clear() { memset(w, 0, sizeof(w)); n = 0; } void insert(int u, int v, int c) { get_max(n, max(u + 1, v + 1)); w[u][v] = c; } int match() { memset(ly, 0, sizeof(ly)); for (int i = 0; i < n; ++i) { lx[i] = -maxint; for (int j = 0; j < n; ++j) { get_max(lx[i], w[i][j]); } } memset(matx, -1, sizeof(matx)); memset(maty, -1, sizeof(maty)); for (int i = 0; i < n; ++i) { memset(fx, false, sizeof(fx)); memset(fy, false, sizeof(fy)); for (int j = 0; j < n; j++) slk[j] = maxint; if (!dfs(i)) { --i; int p = maxint; for (int j = 0; j < n; j++) if (fy[j] == false) p = min(p, slk[j]); for (int j = 0; j < n; ++j) { ly[j] += fy[j] * p; } for (int k = 0; k < n; ++k) { lx[k] -= fx[k] * p; } } } int ans = 0; for (int i = 0; i < n; ++i) { ans += w[maty[i]][i]; } return ans; } bool dfs(int u) { fx[u] = 1; for (int v = 0; v < n; ++v) { if (lx[u] + ly[v] > w[u][v]) { if (lx[u] + ly[v] - w[u][v] < slk[v]) slk[v] = lx[u] + ly[v] - w[u][v]; } else if (lx[u] + ly[v] == w[u][v] && fy[v] == false) { fy[v] = true; if (maty[v] == -1 || dfs(maty[v])) { matx[u] = v; maty[v] = u; return true; } } } return false; } }G;int n, m;vector<int> e[maxn], d[maxn], eid[maxn], sta;int v[maxn], cost[maxn];bool dfs(int w, int y) { if (w == y) return true; if (v[w]) return false; v[w] = 1; rep (i, sz(e[w])) { int j = e[w][i]; sta.push_back(eid[w][i]); if (dfs(j, y)) return true; sta.pop_back(); } return false;}void add(int x, int y, int z, int id) { e[x].push_back(y); eid[x].push_back(id); d[x].push_back(z);}void init() { G.clear(); scanf("%d%d", &n, &m); rep (i, n) { e[i].clear(); eid[i].clear(); d[i].clear(); } rep (i, n - 1) { int x, y, z; scanf("%d%d%d", &x, &y, &z); x--, y--; cost[i] = z; add(x, y, z, i); add(y, x, z, i); } repf (j, n - 1, m - 1) { int x, y, z; scanf("%d%d%d", &x, &y, &z); x--, y--; cost[j] = z; sta.clear(); memset(v, 0, sizeof(v)); dfs(x, y); rep (i, sz(sta)) { if (cost[j] < cost[sta[i]]) { G.insert(j - (n - 1), sta[i], abs(cost[j] - cost[sta[i]])); } } }}void gao() { vector<int> ans; int h = G.match(); rep (i, n - 1) printf("%dn", cost[i] - abs(G.ly[i]), G.ly[i]); repf (i, n - 1, m - 1) printf("%dn", cost[i] + abs(G.lx[i - (n - 1)]), G.lx[i - (n - 1)]);}int main() { int T; scanf("%d", &T); rep (ca, T) { if (ca != 0) puts(""); init(); gao(); } return 0;}
