题目描述

有 $n$ 种类型的男孩和 $2 \cdot n$ 个女孩。男孩的类型用从 $1$ 到 $n$ 的整数编号，而女孩用从 $1$ 到 $2 \cdot n$ 的整数编号。

第 $i$ 种类型的男孩有 $c_i$ 个，这 $c_i$ 个男孩中的每一个都喜欢编号为 $a_i$ 和 $b_i$ 的女孩。

求一个最大的男孩集合的大小，使得对于该集合中的任意两个男孩，至少存在一个女孩被他们两人都喜欢。

本题中，每个测试点包含多组输入数据。你需要对每组数据独立求解。

输入格式

第一行包含一个整数 $T$ $(1 \le T \le 500)$ —— 输入数据的组数。接下来是各组数据的描述。

每组数据的第一行包含一个整数 $n$ $(1 \le n \le 7 \cdot 10^5)$。

接下来的 $n$ 行，每行包含三个整数 $a_i$, $b_i$, $c_i$ $(1 \le a_i < b_i \le 2 \cdot n, 1 \le c_i \le 10^9)$ —— 对应类型男孩的参数。

保证对于任意 $1 \le i < j \le n$，满足 $a_i \ne a_j$ 或 $b_i \ne b_j$。

保证单个测试点中所有输入数据的 $n$ 之和不超过 $7 \cdot 10^5$。

输出格式

对于每组输入数据，输出一行一个整数 —— 满足条件的最大男孩集合的大小。

3
2
1 2 3
3 4 5
5
1 2 1
1 3 4
4 5 2
3 4 2
1 4 3
4
1 2 3
2 3 4
3 5 4
1 3 2

5
9
10

提示

设 $S$ 为单个测试点中所有输入数据的 $n$ 之和，$K$ 为单个测试点中所有 $c_i$ 之和。

• （$5$ 分）：$n \le 5$；
• （$11$ 分）：$S \le 100$；
• （$7$ 分）：每个女孩最多被两种类型的男孩喜欢；
• （$10$ 分）：$S \le 3000$；
• （$23$ 分）：$S \le 3 \cdot 10^5$；
• （$19$ 分）：$K \le 10^7$；
• （$25$ 分）：无额外限制。

对样例第二组输入数据的解释：

• 如果我们选择类型为 2、4 和 5 的男孩，我们可以得到答案 9。也就是说，被选中的男孩喜欢的女孩对 $(a_i, b_i)$ 为 $(1, 3)$、$(3, 4)$ 和 $(1, 4)$。
• 很容易看出，对于这个集合中的任意一对男孩，都存在至少一个他们共同喜欢的女孩。