BaoBao 正在一棵有 $n$ 个顶点和 $(n - 1)$ 条带权边的有根树上玩游戏。游戏开始时，一枚棋子被放置在树的根节点，即顶点 1。
在每一步中，BaoBao 可以执行以下四种操作之一：
- 将棋子沿边从当前顶点移动到某个子节点。此操作将花费 BaoBao $w$ 的价值，其中 $w$ 是该边的权重。
- 将棋子跳回顶点 1。此操作是免费的，不会花费 BaoBao 任何价值。
- 在棋子所在的当前顶点设置一个“存档点”。如果之前已经在其他顶点设置过存档点，则旧顶点上的存档点将被移除（因此树上同一时间最多只能有一个存档点）。此操作是免费的，不会花费 BaoBao 任何价值。
- 将棋子跳回存档点（执行此操作前必须已设置存档点）。此操作是免费的，不会花费 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。