#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

typedef long long cat;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

struct fin {
	vector<cat> T;
	int sz;
	fin() {}
	fin(int N): sz(N) {T.resize(N+10,0);}

	int lastone(int x) {
		return x&(x^(x-1));
	}

	void put(int pos, int val) {
//		cerr << "P " << pos << " " << sz << "\n";
		for(int i =pos+1; i < sz; i +=lastone(i)) T[i] +=val;
	}

	cat get(int pos) {
		cat ret =0;
//		cerr << "G " << pos << "\n";
		for(int i =pos+1; i > 0; i -=lastone(i)) ret +=T[i];
		return ret;
	}
};

// global vars used for holding the current graph state
vector< vector< pair<int,cat> > > G1, G2;
vector<cat> A, B;
vector< pair<int,int> > I;
vector<int> S, S2, dep, Par[20];
vector<bool> lives, exists, exists2;
fin F_sumA, F_sumB, F_sum1;
int Comp_sz;
vector<int> id_plus, id_minus;

void DFS0(int R, int par, vector< vector<int> > &comp) {
	comp[Comp_sz].push_back(R);
	S2[R] =1;
	ALL_THE(G2[R],it) if(exists2[it->ff] && it->ff != par) {
		B[it->ff] =B[R]+it->ss;
		if(R == par) comp[++Comp_sz].clear();
		DFS0(it->ff,R,comp);
		S2[R] +=S2[it->ff];
	}
}

vector< vector<int> > Comp(100000);

cat calc_sum(int R) {
	// find a centroid
	Comp_sz =0;
	Comp[0].clear();
	DFS0(R,R,Comp);
	int c =R;
	for(int i =0; i <= Comp_sz; i++) ALL_THE(Comp[i],it) if(S2[R] <= 2*S2[*it]) {
		bool is_cent =true;
		ALL_THE(G2[*it],jt)
			if(S2[jt->ff] < S2[*it] && 2*S2[jt->ff] > S2[R]) is_cent =false;
		if(is_cent) c =*it;
	}
	Comp_sz =0;
	Comp[0].clear();
	B[c] =0;
	DFS0(c,c,Comp);

	vector< pair<cat,int> > sorted;
	for(int i =0; i <= Comp_sz; i++) ALL_THE(Comp[i],it) if(lives[*it]) {
		sorted.push_back(make_pair(B[*it]-A[*it],*it+1));
		sorted.push_back(make_pair(A[*it]-B[*it],-*it-1));
	}
	sort(begin(sorted),end(sorted));
	for(int i =0; i < (int)sorted.size(); i++) {
		if(sorted[i].ss > 0) id_plus[sorted[i].ss-1] =i;
		else id_minus[-sorted[i].ss-1] =i;
	}

	cat ret =0, sumA =0;
	int n =0;
	F_sum1.sz =sorted.size()+10;
	F_sumA.sz =sorted.size()+10;
	F_sumB.sz =sorted.size()+10;
	for(int i =0; i <= Comp_sz; i++) {
		ALL_THE(Comp[i],it) if(lives[*it]) {
			int id =id_minus[*it];
			int n_le =F_sum1.get(id);
			int n_gt =n-n_le;
			ret +=F_sumB.get(id)+n_le*B[*it];
			ret +=sumA-F_sumA.get(id)+n_gt*A[*it];
		}
		ALL_THE(Comp[i],it) if(lives[*it]) {
			int id =id_plus[*it];
			F_sum1.put(id,1);
			n++;
			F_sumA.put(id,A[*it]);
			sumA +=A[*it];
			F_sumB.put(id,B[*it]);			
		}
	}
	for(int i =0; i <= Comp_sz; i++) ALL_THE(Comp[i],it) if(lives[*it]) {
		int id =id_plus[*it];
		F_sum1.put(id,-1);
		F_sumA.put(id,-A[*it]);
		F_sumB.put(id,-B[*it]);
	}

	exists2[c] =0;
	ALL_THE(G2[c],it) if(exists2[it->ff])
		ret +=calc_sum(it->ff);

	return ret;
}

void DFS(int R, int par, vector<int> &comp) {
	comp.push_back(R);
	S[R] =1;
	ALL_THE(G1[R],it) if(exists[it->ff] && it->ff != par) {
		A[it->ff] =A[R]+it->ss;
		DFS(it->ff,R,comp);
		S[R] +=S[it->ff];
	}
}

int maxdep;

void DFS2(int R, int par, vector<int> &comp2) {
	comp2.push_back(R);
	Par[0][R] =par;
	for(int i =1; i < maxdep; i++) Par[i][R] =Par[i-1][Par[i-1][R]];
	I[R].ss =I[R].ff+1;
	ALL_THE(G2[R],it) if(exists2[it->ff] && it->ff != par) {
		I[it->ff].ff =I[R].ss;
		B[it->ff] =B[R]+it->ss;
		dep[it->ff] =dep[R]+1;
		DFS2(it->ff,R,comp2);
		I[R].ss =I[it->ff].ss;
	}
}

void DFS20(int R, int par) {
	ALL_THE(G2[R],it) if(exists2[it->ff] && it->ff != par) {
		B[it->ff] =B[R]+it->ss;
		DFS20(it->ff,R);
	}
}

int LCA(int u, int v) {
	if(dep[v] < dep[u]) swap(u,v);
	for(int k =maxdep-1; k >= 0; k--) if(dep[Par[k][v]] >= dep[u]) 
		v =Par[k][v];
	if(u == v) return u;
	for(int k =maxdep-1; k >= 0; k--) if(Par[k][u] != Par[k][v]) {
		u =Par[k][u];
		v =Par[k][v];
	}
	return Par[0][u];
}

vector<int> comp, comp2;

cat solve(int R) {
	// find a centroid
	comp.clear();
	DFS(R,R,comp);
	int c =R;
	ALL_THE(comp,it) if(S[R] <= 2*S[*it]) {
		bool is_cent =true;
		ALL_THE(G1[*it],jt)
			if(S[jt->ff] < S[*it] && 2*S[jt->ff] > S[R]) is_cent =false;
		if(is_cent) c =*it;
	}
	comp.clear();
	I[c].ff =A[c] =B[c] =dep[c] =0;
	DFS(c,c,comp);

	comp2.clear();
	maxdep =0;
	while((1<<maxdep) < (int)comp.size()) maxdep++;
	DFS2(c,c,comp2);
	cat ret =calc_sum(c);
	ALL_THE(comp2,it) exists2[*it] =1;

	B[c] =0;
	DFS20(c,c);
	exists[c] =0;
	vector< vector< pair< pair<int,int>, cat> > > E(G1[c].size());
	vector< vector<int> > liveV(G1[c].size());
	vector< vector<int> > allV(G1[c].size());
	vector< pair<int,int> > comp_byI;	
	stack<int> st;
	ALL_THE(G1[c],it) if(exists[it->ff]) {
		comp.clear();
		DFS(it->ff,it->ff,comp);
		comp_byI.clear();
		ALL_THE(comp,jt) if(lives[*jt]) {
			comp_byI.push_back(make_pair(I[*jt].ff,*jt));
			liveV[it-begin(G1[c])].push_back(*jt);
		}
		sort(begin(comp_byI),end(comp_byI));
		vector< pair<int,int> > V =comp_byI; // all vertices
		for(int i =1; i < (int)comp_byI.size(); i++) {
			int u =comp_byI[i-1].ss, v =comp_byI[i].ss;
			int l =LCA(u,v);
			V.push_back(make_pair(I[l].ff,l));
		}
		sort(begin(V),end(V));
		V.resize(unique(begin(V),end(V))-begin(V));
		ALL_THE(V,jt) allV[it-begin(G1[c])].push_back(jt->ss);
		for(int i =0; i < (int)V.size(); i++) {
 			while(!st.empty() && I[st.top()].ss <= V[i].ff) st.pop();
			if(!st.empty()) E[it-begin(G1[c])].push_back(make_pair(make_pair(st.top(),V[i].ss),B[V[i].ss]-B[st.top()]));
			st.push(V[i].ss);
		}
		while(!st.empty()) st.pop();
		ALL_THE(comp,it) lives[*it] =0;
	}
	lives[c] =0;
//	cerr << c << " " << ret << endl;

	ALL_THE(G1[c],it) if(exists[it->ff]) {
		auto id =it-begin(G1[c]);
		ALL_THE(liveV[id],jt) lives[*jt] =1;
		ALL_THE(allV[id],jt) G2[*jt].clear();
		ALL_THE(E[id],jt) {
			G2[jt->ff.ff].push_back(make_pair(jt->ff.ss,jt->ss));
			G2[jt->ff.ss].push_back(make_pair(jt->ff.ff,jt->ss));
		}
		ALL_THE(allV[id],jt) exists2[*jt] =1;
		ret -=calc_sum(it->ff);
		ALL_THE(allV[id],jt) exists2[*jt] =1;
		ret +=solve(it->ff);
		ALL_THE(allV[id],jt) lives[*jt] =exists2[*jt] =0;
	}

	return ret;
}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int T;
	cin >> T;
	F_sumA =fin(5000000);
	F_sumB =fin(5000000);
	F_sum1 =fin(5000000);
	for(int t =0; t < T; t++) {
		int N;
		cin >> N;
		cat sumlen =0;
		G1.clear(); G1.resize(N);
		for(int i =0; i < N-1; i++) {
			int a,b,c;
			cin >> a >> b >> c;
//			if(N > 10000) c /=200;
			sumlen +=c;
			G1[--a].push_back(make_pair(--b,c));
			G1[b].push_back(make_pair(a,c));
		}
		G2.clear(); G2.resize(N);
		for(int i =0; i < N-1; i++) {
			int a,b,c;
			cin >> a >> b >> c;
//			if(N > 10000) c /=200;
			sumlen +=c;
			G2[--a].push_back(make_pair(--b,c));
			G2[b].push_back(make_pair(a,c));
		}
		lives.clear(); lives.resize(N,1);
		exists.clear(); exists.resize(N,1);
		exists2.clear(); exists2.resize(N,1);
		S.resize(N);
		S2.resize(N);
		A.resize(N);
		B.resize(N);
		I.resize(N);
		dep.resize(N);
		id_plus.resize(N);
		id_minus.resize(N);
		for(int i =0; i < 20; i++) Par[i].resize(N);
		cout << solve(0) << "\n";
	}
	return 0;}

// look at my code
// my code is amazings