题目描述

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

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

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

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

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

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

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

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

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

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

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

输入格式

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

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

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

节点编号从$\red {1}$开始。

输出格式

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

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

样例

输入样例

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

输出样例

26

提示

$\red {N≤2\times 10^5}$