You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

树木是自然景观的重要组成部分，因为它们可以防止土壤侵蚀，并在其树叶中及其下方提供特定的气候庇护生态系统。研究表明，树木在生产氧气和减少大气中的二氧化碳方面起着重要作用，还可以调节地面温度。它们在园林设计和农业中也是重要的元素，既因为它们的美学吸引力，也因为它们的果园作物（如苹果）。木材也是常见的建筑材料。

题目描述

树在许多世界神话中也扮演着亲密的角色。许多学者对树的一些特殊属性感兴趣，例如树的中心、树的计数、树的着色等。树的累积度 $A(x)$ 就是其中的一种属性。

我们这么定义 $A(x)$：

• 树的每一条边都有一个正容量。
• 树中度为 $1$ 的节点被称为终端节点。
• 每条边的流量不能超过其容量。
• $A(x)$ 是节点 $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$。