#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long int
#define f(i,x,n) for(int i=x;i<n;++i)
// ============================================================================================================
class Graph {
int V; //vertices
list<pair<int, int>> *l; //adjacency list list of pointers to list
// since it is a weighted graph hence we are storeing pair
//x --> (y,cost)
public:
Graph(int v) {
V = v;
l = new list<pair<int, int>>[V];
}
void addEdge(int u, int v, int cost) {
l[u].push_back({v, cost}); //Segmentation fault
l[v].push_back({u, cost});
}
int min(int a, int b) {
if (a > b) return b;
else return a;
}
int dfsHelper(int n, bool *visited, int *count, int &ans) {
visited[n] = true;
int res;
for (auto i = l[n].begin(); i != l[n].end(); ++i) {
if (!visited[n]) {
res = dfsHelper((*i).first, visited, count, ans);
ans += 2 * ((*i).second) * min(res, V - res);
count[n] += res;
}
}
return count[n];
}
int dfs() {
bool *visited = new bool[V];
int *count = new int[V]; // count is for storing the count
// of each node
for (int i = 0; i < V; ++i) {
visited[i] = false;
count[i] = 1;
}
int ans = 0;
dfsHelper(0, visited, count, ans);
return ans;
}
};
int32_t main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int x, y, z;
Graph g(n);
f(i, 0, n - 1) {
cin >> x >> y >> z;
g.addEdge(x, y, z);
}
int ans = g.dfs();
cout << ans << endl;
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2luY2x1ZGU8ZXh0L3BiX2RzL2Fzc29jX2NvbnRhaW5lci5ocHA+CiNpbmNsdWRlPGV4dC9wYl9kcy90cmVlX3BvbGljeS5ocHA+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwp1c2luZyBuYW1lc3BhY2UgX19nbnVfcGJkczsKCgojZGVmaW5lIGludCAJCQkJCWxvbmcgbG9uZyBpbnQKI2RlZmluZSBmKGkseCxuKQkJCSAgICBmb3IoaW50IGk9eDtpPG47KytpKQoKLy8gPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09CgpjbGFzcyBHcmFwaCB7CgoJaW50IFY7IC8vdmVydGljZXMKCWxpc3Q8cGFpcjxpbnQsIGludD4+ICpsOyAvL2FkamFjZW5jeSBsaXN0IGxpc3Qgb2YgcG9pbnRlcnMgdG8gbGlzdAoJLy8gc2luY2UgaXQgaXMgYSB3ZWlnaHRlZCBncmFwaCBoZW5jZSB3ZSBhcmUgc3RvcmVpbmcgcGFpcgoJLy94IC0tPiAoeSxjb3N0KQoKcHVibGljOgoJR3JhcGgoaW50IHYpIHsKCQlWID0gdjsKCQlsID0gbmV3IGxpc3Q8cGFpcjxpbnQsIGludD4+W1ZdOwoJfQoKCXZvaWQgYWRkRWRnZShpbnQgdSwgaW50IHYsIGludCBjb3N0KSB7CgkJbFt1XS5wdXNoX2JhY2soe3YsIGNvc3R9KTsgLy9TZWdtZW50YXRpb24gZmF1bHQKCQlsW3ZdLnB1c2hfYmFjayh7dSwgY29zdH0pOwoJfQoKCWludCBtaW4oaW50IGEsIGludCBiKSB7CgkJaWYgKGEgPiBiKSByZXR1cm4gYjsKCQllbHNlIHJldHVybiBhOwoJfQoKCWludCBkZnNIZWxwZXIoaW50IG4sIGJvb2wgKnZpc2l0ZWQsIGludCAqY291bnQsIGludCAmYW5zKSB7CgoJCXZpc2l0ZWRbbl0gPSB0cnVlOwoJCWludCByZXM7CgkJZm9yIChhdXRvIGkgPSBsW25dLmJlZ2luKCk7IGkgIT0gbFtuXS5lbmQoKTsgKytpKSB7CgkJCWlmICghdmlzaXRlZFtuXSkgewoJCQkJcmVzID0gZGZzSGVscGVyKCgqaSkuZmlyc3QsIHZpc2l0ZWQsIGNvdW50LCBhbnMpOwoJCQkJYW5zICs9IDIgKiAoKCppKS5zZWNvbmQpICogbWluKHJlcywgViAtIHJlcyk7CgkJCQljb3VudFtuXSArPSByZXM7CgkJCX0KCQl9CgkJcmV0dXJuIGNvdW50W25dOwoJfQoKCWludCBkZnMoKSB7CgkJYm9vbCAqdmlzaXRlZCA9IG5ldyBib29sW1ZdOwoJCWludCAqY291bnQgPSBuZXcgaW50W1ZdOyAvLyBjb3VudCBpcyBmb3Igc3RvcmluZyB0aGUgY291bnQKCQkvLyBvZiBlYWNoIG5vZGUKCgkJZm9yIChpbnQgaSA9IDA7IGkgPCBWOyArK2kpIHsKCQkJdmlzaXRlZFtpXSA9IGZhbHNlOwoJCQljb3VudFtpXSA9IDE7CgkJfQoKCQlpbnQgYW5zID0gMDsKCQlkZnNIZWxwZXIoMCwgdmlzaXRlZCwgY291bnQsIGFucyk7CgkJcmV0dXJuIGFuczsKCX0KfTsKCmludDMyX3QgbWFpbigpIHsKCglpbnQgdDsKCWNpbiA+PiB0OwoJd2hpbGUgKHQtLSkgewoJCWludCBuOwoJCWNpbiA+PiBuOwoKCQlpbnQgeCwgeSwgejsKCQlHcmFwaCBnKG4pOwoJCWYoaSwgMCwgbiAtIDEpIHsKCQkJY2luID4+IHggPj4geSA+PiB6OwoJCQlnLmFkZEVkZ2UoeCwgeSwgeik7CgkJfQoKCQlpbnQgYW5zID0gZy5kZnMoKTsKCgkJY291dCA8PCBhbnMgPDwgZW5kbDsKCX0KCXJldHVybiAwOwp9Cg==