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⁵
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