In a tree, a tripath is a set of 3 non-intersecting paths which begin from the same node.

In other words, a tripath is a set of 3 such paths which originate from the same node of a tree and have no nodes in common apart from the starting node.

The length of a tripath is the sum of all edges on the tripath.

Note: Any path out of the 3 paths in a tripath can be of zero length. So a single node is also a tripath of length = 0.

Trimeter is defined as the length of longest tripath.

You are given a Tree of N nodes and you are required to find the trimeter of the tree.

Input Format:
- First line of input contains an integer T denoting the numebr of test cases.
- Each test case begins with a single integer N which denotes the number of nodes in the tree.
- The following N-1 lines of the format x y w which denote that there is an edge between node x and node y of weight w.

Output Format:
For each test case print a line with the Trimeter of the tree.

Constraints:
1 ≤ T ≤ 10

1 ≤ N ≤ 10

^{5}
1 ≤ x, y ≤ N

-1000 ≤ w ≤ 1000

It is guarenteed that the given graph is a valid tree.

Sample Input:
1

5

1 2 -5

1 3 30

2 4 15

2 5 15

Sample Output:
55

Explanation:
Here in the optimal Tripath, the common starting node is 2 and the paths are:

2->1->3

2->4

2->5