A magical tree with \(N\) vertices and \(N-1\) edges is provided to you. Each of the \(N-1\) edges have some positive weight. Assuming there are \(X\) edges in the simple path between vertices \(A\) and \(B\), then the separation between the vertices \(A\) and \(B\) can be determined using the following formula:

• (Total weights of all the edges along the simple path between vertices \(A\) and \(B\)) × (\(X\%3\))

Now, the mystical value for each vertex is defined as the sum of the separation between this vertex & every other vertex. Your task is to determine the minimum mystical value that a vertex has in the given magical tree.

Note: A simple path is a path in a tree that does not have repeating vertices.

Input format

• The first line contains a single integer \(T\), which denotes the number of test cases.
• For each test case:
  • The first line contains \(N\) denoting the number of vertices in the tree.
  • The following \(N-1\) lines contain 3 space-separated integers, \(u\), \(v\), and \(w\) indicating that there is an edge between vertices \(u\) & \(v\) of weight  \(w\).

Output format

For each test case, print the minimum mystical value that a vertex has in the given magical tree in a new line.

Constraints

\(1 \leq T \leq 10^5 \\ 3 \leq N \leq 10^6 \\ 1≤u,v≤N\\ 1≤w≤10^6 \\ \text{The sum of all values of N over all test cases doesn't exceed } 10^6 \)