#include <bits/stdc++.h>
using namespace std;
#define pii pair <int, int>
#define mp make_pair
#define fi first
#define se second
void gi(int &x) {char ch = getchar(); x = 0; while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();}

typedef void (*func)(int, int);//process(x, dis)
typedef void (*proc)();
typedef long long ll;

int n; ll ans;
const int sz = 202020;

class DS {
public:
  bool prepared;
  pair <int, pair <ll, ll> > P[sz];
  int L;
  void add_pt(int d1, int d2) {P[++L] = mp(d1 - d2, mp(d1, d2));}
  void prepare() {
    sort(P + 1, P + L + 1); P[L + 1] = mp(0, mp(0, 0));
    for (int i = 1; i <= L; i++) P[i].se.fi += P[i - 1].se.fi;
    for (int i = L; i; i--) P[i].se.se += P[i + 1].se.se;
  }
  ll query(int d1, int d2) {
    if (!prepared) prepare(), prepared = 1;
    int s = d2 - d1, tn = 131072, ans = 0;
    for (; tn; tn >>= 1) if (ans + tn <= L && P[ans + tn].fi < s) ans += tn;
    return P[ans].se.fi + P[ans + 1].se.se + 1ll * ans * d1 + 1ll * (L - ans) * d2;
  }
  void clr(){prepared = 0; L = 0;}
} D1, D2;

class Tree {
public:
  int node[sz], next[sz << 1], to[sz << 1], w[sz << 1], e, N, deg[sz], p[sz];
  void ins0(int x, int y, int v) {e++; next[e] = node[x]; node[x] = e; to[e] = y; w[e] = v;}
  void bis0(int x, int y, int v) {ins0(x, y, v); ins0(y, x, v);}
  int o(int x) {int v = p[x]; if (deg[v] == 2) {p[x] = ++N; bis0(v, p[x], 0); deg[p[x]] = 1;} return p[x];}
  void ins(int x, int y, int v) {x = o(x); y = o(y); bis0(x, y, v); deg[x]++; deg[y]++;}

  int q[sz], f[20][sz], dep[sz], d[sz];
  void bfs() {
    int i, j, k, l, r;
    for (q[l = r = 1] = 1; l <= r; )
      for (j = node[k = q[l++]]; j; j = next[j])
	if (to[j] != f[0][k]) f[0][to[j]] = k, dep[to[j]] = dep[k] + 1, d[to[j]] = d[k] + w[j], q[++r] = to[j];
    for (j = 1; j < 20; j++) for (i = 1; i <= N; i++) f[j][i] = f[j - 1][f[j - 1][i]];
  }
  int LCA(int x, int y) {
    int d = dep[x] - dep[y], j;
    if (d < 0) return LCA(y, x);
    for (j = 0; d; d >>= 1, j++) if (d & 1) x = f[j][x];
    if (x == y) return x;
    for (j = 19; j >= 0; j--) if (f[j][x] != f[j][y]) x = f[j][x], y = f[j][y];
    return f[0][x];
  }
  int dis(int x, int y) {return d[x] + d[y] - (d[LCA(x, y)] << 1);}

  int pos[sz], seq[sz], ir[sz], I;
  void dfs(int x, int p) {
    seq[pos[x] = ++I] = x;
    for (int j = node[x]; j; j = next[j]) if (to[j] != p) dfs(to[j], x);
    ir[x] = I;
  }
  int is_ancestor(int p, int c) {return pos[c] >= pos[p] && ir[c] <= ir[p];}
  int sta[sz], top;
  void ens(int x); void des();
  int create_auxtree(int pts[], int l);

#define _(x) ((x) & 1 ? (x) + 1 : (x) - 1)
  bool vis[sz << 1];
  int siz[sz];
  int getme(int x, int p, int s, int &me, int &mv) {
    siz[x] = 1;
    for (int j = node[x]; j; j = next[j])
      if (to[j] != p && !vis[j]) {
	getme(to[j], x, s, me, mv);
	siz[x] += siz[to[j]];
	int k = max(siz[to[j]], s - siz[to[j]]);
	if (k < mv) mv = k, me = j;
      }
  }

  void Dfs(int x, int p, int d, func f) {
    f(x, d);
    for (int j = node[x]; j; j = next[j]) if (to[j] != p && !vis[j]) Dfs(to[j], x, d + w[j], f);
  }

  void dac(int x, int p, func f1, func f2, proc solve) {
    int s, me, mv;
    getme(x, p, 1000000000, me, mv); s = siz[x]; if (s == 1) return;
    mv = 1000000000; getme(x, p, s, me, mv);
    int u = to[me], v = to[_(me)]; vis[me] = vis[_(me)] = 1;
    Dfs(u, v, 0, f1); Dfs(v, u, w[me], f2); solve();
    dac(u, v, f1, f2, solve); dac(v, u, f1, f2, solve);
  }
} T1, T2, auxtree;

void Tree::ens(int x){sta[++top] = x;}
void Tree::des(){
  int x = sta[top];
  int y = sta[--top];
  int l = dis(x, y);
  auxtree.ins(x, y, l);
}

int Tree::create_auxtree(int pts[], int l) {
  int i, u = pts[1];
  for (i = 1; i <= l; i++) pts[i] = pos[pts[i]];
  sort(pts + 1, pts + l + 1);
  for (i = 1; i <= l; i++) u = LCA(u, pts[i] = seq[pts[i]]);
  ens(u);
  for (i = 1; i <= l; i++) {
    int t = LCA(sta[top], pts[i]);
    while (top > 1 && !is_ancestor(sta[top - 1], pts[i])) des();
    if (t != sta[top]){
      if (t != sta[top - 1]){
	sta[top + 1] = sta[top]; sta[top++] = t;
      }
      des();
    }
    if (pts[i] != sta[top]) ens(pts[i]);
  }
  while (top > 1) des(); top = 0; return u;
}

int col[sz], d1[sz], arr[sz], L;
void f1_1(int x, int d) {if (x <= n) {col[x] = 1; d1[x] = d; arr[++L] = x;}}
void f2_1(int x, int d) {if (x <= n) {col[x] = 2; d1[x] = d; arr[++L] = x;}}

void f1_2(int x, int d) {
  if (col[x] == 1) D1.add_pt(d1[x], d);
  if (col[x] == 2) D2.add_pt(d1[x], d);
}
void f2_2(int x, int d) {
  if (col[x] == 1) ans += D2.query(d1[x], d);
  if (col[x] == 2) ans += D1.query(d1[x], d);
}
void solve_2() {D1.clr(); D2.clr();}

void solve_1() {
  int root = T2.create_auxtree(arr, L);
  auxtree.dac(root, -1, f1_2, f2_2, solve_2);
  //clr
  for (int i = 1; i <= L; i++) col[arr[i]] = d1[arr[i]] = 0;
  for (int i = 1; i <= auxtree.e; i++) {
    int x = auxtree.to[i];
    auxtree.node[x] = auxtree.deg[x] = 0; auxtree.p[x] = x;
    auxtree.next[i] = auxtree.to[i] = auxtree.w[i] = auxtree.vis[i] = 0;
  }
  L = auxtree.e = 0; auxtree.N = n;
}

void doit() {
  int i, j, k;
  gi(n);
  for (i = 1; i <= n; i++) T1.p[i] = T2.p[i] = auxtree.p[i] = i;
  T1.N = T2.N = auxtree.N = n;
  for (int p = 1; p < n; p++) {gi(i); gi(j); gi(k); T1.ins(i, j, k);}
  for (int p = 1; p < n; p++) {gi(i); gi(j); gi(k); T2.bis0(i, j, k);}
  T2.bfs(); T2.dfs(1, -1);
  ans = 0; T1.dac(1, -1, f1_1, f2_1, solve_1);
  cout << ans << endl;

  for (i = 1; i <= T1.N; i++) T1.node[i] = T1.deg[i] = T1.p[i] = 0;
  for (i = 1; i <= T1.e; i++) T1.next[i] = T1.to[i] = T1.w[i] = T1.vis[i] = 0; T1.e = 0;
  for (i = 1; i <= T2.N; i++) T2.node[i] = T2.deg[i] = T2.p[i] = T2.dep[i] = T2.d[i] = T2.pos[i] = T2.seq[i] = T2.ir[i] = T2.sta[i] = 0;
  for (j = 0; j < 20; j++) for (i = 1; i <= T2.N; i++) T2.f[j][i] = 0;
  for (i = 1; i <= T2.e; i++) T2.next[i] = T2.to[i] = T2.w[i] = T2.vis[i] = 0;
  T2.e = T2.top = T2.I = 0;
}

int main(){int T; gi(T); while (T--) doit(); return 0;}