题目描述

树木是自然景观的重要组成部分，因为它们能防止侵蚀，并在其枝叶内外提供一个特定的受庇护生态系统。树木还被发现在产生氧气和减少大气中的二氧化碳以及调节地面温度方面发挥着重要作用。它们也是景观设计和农业中的重要元素，既因为其美学吸引力，也因其果园作物（如苹果）。树木的木材是一种常见的建筑材料。

树木在世界许多神话中也扮演着密切的角色。许多学者对寻找树木的奇特属性感兴趣，例如树的中心、树的计数、树的着色。$A(x)$ 就是其中之一。

$A(x)$（节点 $x$ 的累积度）定义如下：

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

由于可能难以理解该定义，下面展示一个例子：

• $A(1)=11+5+8=24$
  详细说明：
  $1\rightarrow2$：$11$
  $1\rightarrow4\rightarrow3$：$5$
  $1\rightarrow4\rightarrow5$：$8$（因为 $1\rightarrow4$ 的容量为 $13$）
• $A(2)=5+6=11$
  详细说明：
  $2\rightarrow1\rightarrow4\rightarrow3$：$5$
  $2\rightarrow1\rightarrow4\rightarrow5$：$6$
• $A(3)=5$
  详细说明：
  $3\rightarrow4\rightarrow5$：$5$
• $A(4)=11+5+10=26$
  详细说明：
  $4\rightarrow1\rightarrow2$：$11$
  $4\rightarrow3$：$5$
  $4\rightarrow5$：$10$
• $A(5)=10$
  详细说明：
  $5\rightarrow4\rightarrow1\rightarrow2$：$10$

树的累积度是其所有节点中最大的累积度。你的任务是计算给定树的累积度。

输入格式

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

输出格式

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

输入样例 1

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

输出样例 1

26

来源

2008年中南地区程序设计竞赛，由国防科技大学主办