Description

树在许多世界神话中也扮演着亲密的角色。许多学者对树的一些特殊属性感兴趣，例如树的中心、树的计数、树的着色等。树的累积度 $A(x)$ 就是其中的一种属性。

我们这么定义 $A(x)$：

• 树的每一条边都有一个正容量。
• 树中度为 $1$ 的节点被称为终端节点。
• 每条边的流量不能超过其容量。
• $A(x)$ 是节点 $x$ 可以流向其他终端节点的最大流量。

树的累积度是指其节点中最大累积度的值。你的任务是找到给定树的累积度。

Input Format

输入的第一行是一个整数 $T$，表示测试用例的数量。每个测试用例的第一行是一个正整数 $n$。接下来的 $n - 1$ 行中的每一行包含三个整数 $x,y,z$，用空格分隔，表示节点 $x$ 和节点 $y$ 之间有一条边，并且这条边的容量为 $z$。节点编号从 $1$ 到 $n$。所有元素都是不超过 $200000$ 的非负整数。可以假设测试数据都是树。

Output Format

对于每个测试用例，在单独的一行输出结果。

1
5
1 2 11
1 4 13
3 4 5
4 5 10

26

Hint

原题中没有提到的数据范围：$T \le 4$，$\sum n \le 2\times 10 ^ 5$。