题目描述

首先看到题目别太开心，这题可不是让你出数据～^_*

背景神马的就忽略了。这题就是给你一棵带边权的树，然后这棵树是某个完全图唯一的最小生成树。问原来的完全图中所有边可能的最小边权和是多少。

完全图是任意两个点之间都有边相连的图。

输入格式

第一行包含一个整数T表示数据组数。

每组数据第一行一个整数N表示点数。

接下来N-1行每行三个整数ai，bi，wi表示最小生成树上ai和bi之间有一条权值为wi的边。

输出格式

输出应有T行，每行表示一组数据的答案。

样例数据

input

2

3

1 2 4

2 3 7

4 

1 2 1

1 3 1

1 4 2

output

19

12

数据规模与约定

20%的数据满足：T≤5，n≤5，wi≤5

另外30%的数据满足：n≤1000，给定的树是一条链

100%的数据满足：T≤10，n≤20000，wi≤10000

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$