题目描述 题目译自 Ukrainian Olympiads in Informatics 2025 Stage 4 Day1 T1. Хлопці та дівчата

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

第 $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)$，分别表示第 $i$ 种类型男生喜欢的两名女生的编号以及该类型男生的数量。

保证对于任意 $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$ 之和。详细子任务附加限制及分值如下表所示：