该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

退役多年的 Hiki，重新复习从前学过的算法时，感到十分艰难。

他最近在学习完全图的最小生成树。你或许觉得这太简单了，可是问题在于原来的数据不幸丢失，只能找到输出的最小生成树数据。现在请你帮帮 Hiki：如何从一棵树找到以它为最小生成树的最小完全图。

更具体地，给出一棵带边权的树，这棵树是某个完全图的唯一最小生成树，Hiki 想知道原来的完全图中所有边最小的可能边权和是多少。注意：此处讨论的边权均为整数。

完全图是任意两个点之间都有边相连的无向图。

Input

第一行包含一个整数 T 表示数据组数。

每组数据第一行一个整数 n 表示点数。

接下来 n-1 行每行三个整数𝑎𝑖 , 𝑏𝑖 , 𝑤𝑖，表示最小生成树上点𝑎𝑖和𝑏𝑖之间有一条权值为𝑤𝑖的边。

Output

共 T 行，每行一个整数，表示每组数据的最小可能边权和。

Samples

2 
3 
1 2 4 
2 3 7 
4 
1 2 1 
1 3 1 
1 4 2

19 
12

Limitation

20%的数据满足：𝑇 ≤ 5，𝑛 ≤ 5，𝑤𝑖 ≤ 5；

另外 30%的数据满足：𝑛 ≤ 1000，给定的树是一条链；

100%的数据满足：𝑇 ≤ 10，𝑛 ≤ 20000，𝑤𝑖 ≤ 10000。