N. The Tree Problem Is Done For
time limit per test
2 с
memory limit per test
256 megabytes
input
standard input
output
standard output

After listening to Mask by Dream, Asahi decided to start wearing a mask and a green hoodie. Unfortunately, this did not change the fact that she is still failing all her classes. Thus, Asahi now turns to you for help on her test.

In the test, Asahi is given a tree with $$$N (1 \le N \le 5 \cdot 10^5)$$$ nodes. The $$$i$$$th edge in the tree between nodes $$$u_i$$$ and $$$v_i$$$ has a weight of $$$w_i (0 \le w_i \le 10^9)$$$. The goal is to choose two node disjoint (cannot share any nodes) paths in the tree. Asahi's score will then be $$$\text{min}(\text{sum of weight of path 1}, \text{sum of weight of path 2})$$$. Asahi wants to score as high as possible on the test, so she asks you to find her maximum possible score.

Input

The first line contains one integer $$$T (1 \le T \le 10)$$$, denoting the number of test cases.

The first line of every test case will contain a single integer $$$N (1 \le N \le 5 \cdot 10^5)$$$, the size of the tree.

The next $$$N - 1$$$ lines of every test case will each contain three integers $$$u_i$$$, $$$v_i$$$, $$$(1 \le u_i, v_i \le N)$$$ and $$$w_i$$$ $$$(0 \le w_i \le 10^9)$$$, denoting the two endpoints and weight of the $$$i$$$th edge respectively.

It is guaranteed that $$$\sum N \le 5 \cdot 10^5$$$.

In testcase $$$1$$$, $$$\sum N \le 50$$$.

In testcases $$$2 - 4$$$, $$$\sum N \le 5000$$$.

In testcases $$$5$$$, $$$w_i = 0$$$.

In testcase $$$6 - 14$$$, $$$\sum N \le 2 \cdot 10^5$$$.

In testcases $$$15 - 20$$$, there are no further restrictions.

Output

For each test case, output a line containing the maximum score Asahi can achieve for that test case.

Example
Input
1
6
1 2 1
2 3 1
1 4 3
4 5 5
4 6 5
Output
2
Note

Idea: oursaco

Preparation: oursaco

Occurrences: Advanced 9