在ICPC Camp中，有 $n$ 个小镇，编号为 $1, 2, ..., n$ 。这 $n$ 个小镇通过 $n-1$ 条普通公路相连接。 第 $i$ 条普通公路的长度为 $c_i$ ，连接了 $a_i$ 和 $b_i$ 两个小镇。保证任意两个小镇都可以通过普通公路互相到达。 现在，Bobo 想要建 $n - 1$ 条高速公路，使得任意两个小镇都可以**仅通过高速公路**互相到达。如果在小镇 $x$ 和小镇 $y$之间建一条高速公路，需要的费用是 $\delta(x, y)$。 其中，$\delta(x, y)$ 表示 小镇 $x$ 和小镇 $y$ 之间**仅通过普通公路**的最短路径的长度。 由于Bobo非常有钱，所以他希望你帮他算出建这 $n - 1$条高速公路的总费用的最大值。

输入包含了 $T$组的测试数据。对于每组测试数据： 第一行包含一个正整数 $n$，接下来的 $n - 1$行中，第 $i$ 行包含三个正整数，分别是 $a_i, b_i, c_i$，代表 $n - 1$条普通公路。 数据范围如下： $1 \le T \le 10$ $1 \leq n \leq 10^5$ $1 \leq a_i, b_i \leq n$ $1 \leq c_i \leq 10^8$

对每组测试数据，均输出一行，包含一个整数，表示最大费用。

https://ac.nowcoder.com/acm/contest/26077/1011