BaoBao 正在一棵有 $n$ 个顶点和 $(n - 1)$ 条带权边的有根树上玩游戏。游戏开始时，一枚棋子被放置在树的根节点，即顶点 1。

在每一步中，BaoBao 可以执行以下四种操作之一：

1. 将棋子沿边从当前顶点移动到某个子节点。此操作将花费 BaoBao $w$ 的价值，其中 $w$ 是该边的权重。
2. 将棋子跳回顶点 1。此操作是免费的，不会花费 BaoBao 任何价值。
3. 在棋子所在的当前顶点设置一个“存档点”。如果之前已经在其他顶点设置过存档点，则旧顶点上的存档点将被移除（因此树上同一时间最多只能有一个存档点）。此操作是免费的，不会花费 BaoBao 任何价值。
4. 将棋子跳回存档点（执行此操作前必须已设置存档点）。此操作是免费的，不会花费 BaoBao 任何价值。

游戏的目标是使用棋子访问树上的每一个叶子节点。请帮助 BaoBao 计算他为了达到目标所必须花费的最小价值。

回想一下，树的叶子节点是指没有子节点的顶点。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($2 \le n \le 200$)，表示树的大小。

接下来的 $(n - 1)$ 行，每行包含三个整数 $u_i, v_i$ 和 $w_i$ ($1 \le u_i, v_i \le n, 1 \le w_i \le 10^9$)，表示树中连接顶点 $u_i$ 和顶点 $v_i$ 的一条权重为 $w_i$ 的边。

保证给定的图是一棵树，且所有测试数据中 $n$ 的总和不超过 2000。

输出格式

对于每组测试数据，输出一行包含一个整数，表示 BaoBao 为达到目标所必须花费的最小价值。

样例

样例输入 1

3
8
1 2 1
3 1 1
2 4 2
5 4 2
6 2 2
3 7 3
8 3 3
8
1 2 1
2 3 1
3 4 1
3 5 1
2 6 1
6 7 1
6 8 1
8
1 2 100
2 3 1
3 4 1
3 5 1
2 6 1
6 7 1
6 8 1

样例输出 1

14
8
107

说明

样例测试数据的树结构如上图所示。

对于第一个样例测试数据，BaoBao 应执行以下操作：移动到 2，在 2 存档，移动到 4，移动到 5，回到存档点 (2)，移动到 6，回到根节点 (1)，移动到 3，在 3 存档，移动到 7，回到存档点 (3)，移动到 8。

对于第二个样例测试数据，BaoBao 应执行以下操作：移动到 2，移动到 3，在 3 存档，移动到 4，回到存档点 (3)，移动到 5，回到根节点 (1)，移动到 2，移动到 6，在 6 存档，移动到 7，回到存档点 (6)，移动到 8。

对于第三个样例测试数据，BaoBao 应执行以下操作：移动到 2，在 2 存档，移动到 3，移动到 4，回到存档点 (2)，移动到 3，移动到 5，回到存档点 (2)，移动到 6，在 6 存档，移动到 7，回到存档点 (6)，移动到 8。