A16567 | Maximize Determinant

如果一个 $n \times n$ 的矩阵 $B$ 满足：对于每一行 $i$，都存在一段连续的列区间 $[l_i, r_i]$（$1 \le l_i \le r_i \le n$），使得该行在区间 $[l_i, r_i]$ 范围内的元素全为 $1$，其他位置全为 $0$，那么称 $B$ 为区间矩阵。形式化地，$B_{i, j} = 1$ 当且仅当 $l_i \le j \le r_i$，否则 $B_{i, j} = 0$。

现在给定一个整数 $n$ 和一个初始的区间矩阵 $A$，用 $n$ 个三元组 $(l_i, r_i, a_i)$ 描述。第 $i$ 行对应的区间是 $[l_i, r_i]$，修改这一行的代价是 $a_i$。

令 $\mathcal{S}$ 表示所有可能的 $n \times n$ 区间矩阵的集合。记 $X$ 为其中行列式的最大值：

$$ X = \max\limits_{B \in \mathcal{S}} \operatorname{det}(B). $$

（注意：$|\mathcal{S}| = \left(\frac{n(n + 1)}{2}\right)^n$，每一行都可以选任意合法区间）

你的目标是将 $A$ 变换成某个区间矩阵 $A'$，使 $\operatorname{det}(A') = X$。为此，你可以进行如下操作任意次：

- 选择一个行索引 $i$（$1 \le i \le n$）和一个新的合法区间 $[L, R]$（$1 \le L \le R \le n$）。
- 将当前第 $i$ 行的区间替换为 $[L, R]$。
- 这次操作的代价为 $a_i$。

请你计算，使最终矩阵的行列式为 $X$ 所需的最小总代价。

每组数据包含若干组测试用例。第一行输入测试用例组数 $t$（$1 \le t \le 5 \cdot 10^4$）。每组测试用例格式如下：

第一行包含一个整数 $n$（$1 \le n \le 10^6$）——矩阵的规模。

接下来的 $n$ 行，每行三个整数 $l_i$、$r_i$、$a_i$（$1 \le l_i \le r_i \le n$，$1 \le a_i \le 10^9$），分别表示第 $i$ 行初始区间和修改代价。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

对于每组测试用例，输出一个整数，表示将矩阵的行列式调整为 $X$ 所需的最小总代价。