// another fine solution by misof
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

typedef pair<int,int> PII;
typedef pair<int, pair<int,int> > TRI;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define SIZE(t) ((int)((t).size()))
#define MAXN 1000123

int T, N;
int boss[MAXN], size[MAXN];

int main() {
  cin >> T;
  while (T--) {
    cin >> N;
    vector<TRI> V;
    int x,y,z;
    REP(n,N-1) { cin >> x >> y >> z; x--; y--; V.push_back(TRI(z,PII(x,y))); }
    REP(n,N) boss[n]=n; 
    REP(n,N) size[n]=1; 

    sort(V.begin(),V.end());
    long long res = 0;
    REP(i,SIZE(V)) {
      int a = V[i].second.first, b = V[i].second.second;
      while (a!=boss[a]) a=boss[a];
      while (b!=boss[b]) b=boss[b];
      long long s1 = size[a], s2 = size[b];
      res += s1*s2*(V[i].first+1)-1;
      if (s1 < s2) { boss[a]=b; size[b]+=size[a]; }
      else { boss[b]=a; size[a]+=size[b]; }
    }
    cout << res << endl;
  }
}
// vim: fdm=marker:commentstring=\ \"\ %s:nowrap:autoread