80分

#include <bits/stdc++.h>
using namespace std;
struct edge {
	long long v, d, ne;
} es[600007];
long long n, t, x, y, z, h[600007], idx = 1, d[300007], dx[300007], ans, f[300007];
void add(int u, int to, int q) {
	es[idx] = {to, q, h[u]}, h[u] = idx, idx++;
	return;
}
void dfs(int u, int fa) {
	dx[u] = 0;
	for (int e = h[u]; e; e = es[e].ne) {
		if (es[e].v == fa) continue;
		dfs(es[e].v, u);
		if (d[es[e].v] == 1) dx[u] += es[e].d;
		else dx[u] += min(dx[es[e].v], es[e].d);
	}
	return;
}
void dp(int u, int fa) {
	for (int e = h[u]; e; e = es[e].ne) {
		if (es[e].v == fa) continue;
		if (d[u] == 1) f[es[e].v] = dx[es[e].v] + es[e].d;
		else if (d[es[e].v] == 1) f[es[e].v] = dx[es[e].v] + min(f[u] - es[e].d, es[e].d);
		else f[es[e].v] = dx[es[e].v] + min(f[u] - min(dx[es[e].v], es[e].d), es[e].d);
		dfs(es[e].v, u);
	}
	return;
}
int main() {
	cin >> t;
	while (t--) {
		memset(d, 0, sizeof(d));
		memset(es, 0, sizeof(es));
		memset(dx,0,sizeof(dx));
		memset(h, 0, sizeof(h));
		memset(f, 0, sizeof(f));
		idx = 1;
		cin >> n;
		for (int i = 1; i < n; i++) {
			cin >> x >> y >> z;
			add(x, y, z), add(y, x, z);
			d[x]++, d[y]++;
		}
		dfs(1, -1);
		f[1] = dx[1], ans = 0;
		dp(1, -1);
		for (int i = 1; i <= n; i++) ans = max(ans, f[i]);
		cout << ans << "\n";
	}
	return 0;
}