题目背景

出题目是一件很费力的事，为一道题出数据则是更加令人痛苦的事情。Wish 现在正在帮一些学弟学妹们出一些信息学竞赛的基础题，但在出数据的过程中遇到了一些棘手的问题……

Wish 出的题目是：找出给定带权图图的最小生成树，为了加大一点难度，给定的图均为无向完全图（即任意两个点均连一条边），并且 Wish 希望这个图中各边的权值尽可能大。

Wish 制作测试数据的方法比较特别，他是先生成一个树，然后再向这个树中加边来构造完全图。但是他发现他的程序有些问题，有的时候最后生成的图的最小生成树并不是开始给定的那个。

由于已经生成了很多组数据，为了检测出哪些数据有问题，他想让你计算出给定的树可构造出的完全图的最小边权值和是多少，于是生成的小于这个和的图的数据就可以筛去了。

题目描述

给定一个树 T，找出一个无向完全图 G，使得 T 是 G 的最小生成树，并且 G 各边的权值之和尽可能小，输出这个最小权值和即可。

每个测试点包含多组数据，第一行一个数 t，表示共 t 组测试数据。

后接 t 组测试数据。

每组数据之前有一个空行。

每组数据的第一行有一个数 n，表示给定树的节点数（节点编号 1-n）。

之后 n-1 行，每行三个数 ai、bi、wi，表示节点 ai 和 bi 之间连有一条边，其权值为 wi。

数据范围

1 <= t <= 20

1 <= n <= 15000

1 <= ai, bi <= n

1 <= wi <= 10000

对于每组测试数据，输出一行，表示求出的最小权值和。