An (n \times n) matrix (B) is called an interval matrix if for each row (i), there exists a contiguous range of columns (l_i, r_i) ((1 \le l_i \le r_i \le n)) filled with ones, while all other elements in the row are zero. Formally, (B_{i, j} = 1) if (l_i \le j \le r_i), and (B_{i, j} = 0) otherwise. You are given an integer (n) and an initial interval matrix (A), described by (n) triples ((l_i, r_i, a_i)). The (i)-th row of (A) corresponds to the interval (l_i, r_i), and (a_i) is the cost associated with modifying this row. Let (\mathcal{S}) be the set of all possible (n \times n) interval matrices. We define (X) as the maximum possible determinant among them: () X = \max\limits_{B \in \mathcal{S}} \operatorname{det}(B). () (Note that (|\mathcal{S}| = \left(\frac{n(n + 1)}{2}\right)^n), as each row can be any valid interval) Your goal is to transform (A) into a matrix (A') such that (\operatorname{det}(A') = X). To achieve this, you can perform the following operation any number of times: Choose a row index (i) ((1 \le i \le n)) and a new valid interval (L, R) ((1 \le L \le R \le n)). Replace the current interval of the (i)-th row with (L, R). The cost of this operation is (a_i). Find the minimum total cost required to make the determinant of the matrix equal to (X). Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 5 \cdot 10^4)). The description of the test cases follows. The first line of each test case contains a single integer (n) ((1 \le n \le 10^6)) — the size of the matrix. The next (n) lines describe the rows of the matrix (A). The (i)-th of these lines contains three integers (l_i), (r_i), and (a_i) ((1 \le l_i \le r_i \le n), (1 \le a_i \le 10^9)) — the interval boundaries and the cost of modifying the $