题目描述

学校里有 $N$ 个教室，它们之间由 $N-1$ 条走廊连接，形成一棵树的结构，每条走廊有一个长度值。现在学校计划在任意两个教室之间都开通直达走廊，使得整个学校成为一个完全图。但有一个要求：原来的 $N-1$ 条走廊构成的树必须是新图的唯一最小生成树。新开通的走廊长度必须是正整数。请问所有新开通走廊的长度之和最少是多少？

输入格式

第一行包含整数 $t$，表示共有 $t$ 组测试数据。

对于每组测试数据，第一行包含整数 $N$。

接下来 $N-1$ 行，每行三个整数 $X, Y, Z$，表示教室 $X$ 与教室 $Y$ 之间有一条长度为 $Z$ 的走廊。

输出格式

每组数据输出一个整数，表示新开通走廊长度总和的最小值。每个结果占一行。

样例

2
3
1 2 2
1 3 3
4
1 2 3
2 3 4
3 4 5

4
17

提示

$1 \le t \le 10$，$1 \le N \le 6000$，$1 \le Z \le 100$