题目描述

有 $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 10^7)$。

接下来的 $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$ 之和不超过 $10^7$。

输出格式

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

样例 1 输入

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

样例 1 输出

5
9
10

数据范围

令 $S=\sum n$，则对于全部数据：$1 \le S \le 10^7$，$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$。

• 子任务 1（$10$ 分）：$n \le 5$；
• 子任务 2（$10$ 分）：$S\le 7\cdot 10^5$，每个女生最多被两种类型的男生喜欢；
• 子任务 3（$20$ 分）：$S \le 3000$；
• 子任务 4（$20$ 分）：$S\le 7\cdot 10^5$；
• 子任务 5（$40$ 分）：无额外限制。