题目描述

有一个树形的水系，由 $N-1$ 条河道和 $N$ 个交叉点组成。

我们可以把交叉点看作树中的节点，编号为 $1 \sim N$，河道则看作树中的无向边。

每条河道都有一个容量，连接 $x$ 与 $y$ 的河道的容量记为 $c(x,y)$。

河道中单位时间流过的水量不能超过河道的容量。

有一个节点是整个水系的发源地，可以源源不断地流出水，我们称之为源点。

除了源点之外，树中所有度数为 $1$ 的节点都是入海口，可以吸收无限多的水，我们称之为汇点。

也就是说，水系中的水从源点出发，沿着每条河道，最终流向各个汇点。

在整个水系稳定时，每条河道中的水都以单位时间固定的水量流向固定的方向。

除源点和汇点之外，其余各点不贮存水，也就是流入该点的河道水量之和等于从该点流出的河道水量之和。

整个水系的流量就定义为源点单位时间发出的水量。

在流量不超过河道容量的前提下，求哪个点作为源点时，整个水系的流量最大，输出这个最大值。

输入格式

输入第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组测试数据，第一行包含整数 $N$。

接下来 $N-1$ 行，每行包含三个整数 $x,y,z$，表示 $x$，$y$ 之间存在河道，且河道容量为 $z$。

节点编号从 $1$ 开始。

输出格式

每组数据输出一个结果，每个结果占一行。

数据保证结果不超过 $2^{31}-1$。

样例

输入样例：

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

输出样例：

26

样例解释

$N=5$，树的结构： 边： 1-2 容量 11 1-4 容量 13 3-4 容量 5 4-5 容量 10

图形：

    2
    |
1---4---5
    |
    3

选择一个点作为源点（可以流出任意多水），其他度为 1 的点作为汇点（可吸收任意多水），要求每条边流量不超过容量，且除源点和汇点外流量守恒。

我们需要最大化从源点流出的总流量（等于所有汇点流入的总和）。

对于树来说，如果源点不是叶子（度>1），那么流量由源点相邻的边的容量之和的某种分配决定。
实际上，问题等价于：选择一个源点，使得从该源点到所有叶子的流量最大。
可以证明，最大流量等于：以该点为根时，流向每个儿子的最大流量之和，其中流向某个儿子的最大流量为 min(边容量, 该儿子子树的“瓶颈”)。

换根 DP 可解。

样例中，若源点为 4：

• 向 1 方向最大流量 min(13, 11) = 11（因为 1 是叶子？实际上 1 度数为 2，不是叶子，但 1 向 2 方向只能流 11，所以整体为 min(13,11) = 11）
• 向 3 方向最大流量 min(5) = 5（3 是叶子）
• 向 5 方向最大流量 min(10) = 10（5 是叶子） 总流量 11+5+10 = 26。

其他点作为源点达不到 26，所以输出 26。

数据范围

• $N \le 2 \times 10^5$

时空限制

• 时间限制：2 秒
• 空间限制：64 MB