Description

$a$ $($$x$ $)$表示树中节点$x$ 的累积度，定义如下：

①树的每个边都有一个正容量；

②树中度为$1$的节点叫作终端；

③每条边的流量都不可以超过其容量；

④$a$ $($$x$ $)$是节点$x$ 可以流向其他终端节点的最大流量。

示例如下图所示。

$（1)a (1)=11+5+8=24$

$（2）a (2)=5+6=11$

$（3）a (3)=5$

$（4）a (4)=11+5+10=26$

$（5）a (5)=10$

树的累积度是树中节点的最大累积度。

Input

第$1$行是一个整数$t$ ，表示测试用例的数量。每个测试用例的第$1$行都是一个正整数$n$ ，表示节点数，节点编号为$1$～$n$ 。下面$n$ -$1$行中的每一行都包含三个整数$x$ 、$y$ 、$z$ ，表示在节点$x$ 和节点$y$ 之间有一条边容量为$z$ 。所有元素都是不超过$2$$0$$0$$0$$0$$0$的非负整数。

Output

对每个测试用例，都单行输出树的累积度。

Samples

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

26

来源

POJ3585