题目背景

河谷里的水网可以抽象成一棵树：每条河道有各自的输水上限，水从某个节点出发，沿着河道一路向下游输送，最终注入没有下游出口的端点。研究者们想知道，整片水网至多能同时输送多少水。

题目描述

给定一棵带权树，每条边都有一个正的容量。树中度为 $1$ 的节点称为端点。从某个节点 $x$ 出发，可以把若干单位的「流量」沿边送往其他端点，但每条边上通过的流量不能超过该边的容量。记 $A(x)$ 为从 $x$ 出发、最终到达各个端点的最大总流量。整棵树的「累积度」定义为所有节点中 $A(x)$ 的最大值。请求出这棵树的累积度。

输入格式

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

输出格式

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

样例

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

26

提示

数据范围：$T \le 4$，$\sum n \le 2\times 10 ^ 5$。