问题 I: 未来城市

内存限制:524 MB 时间限制:3 S
题面:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

在一座科技先进的城市中,有 nn 个能源核心,编号从 11 到 nn,每个核心都蕴含独特的能量。为了优化城市运行,工程师们设计了 mm 个能源利用项目,编号从 11 到 mm。第 ii 个项目可以使用能源核心 aiai 或者 bibi 中的其中一个来激活,并且激活该项目可以获得价值 wiwi。然而,每个能源核心的能量有限,最多只能支持一个项目。你的任务是选择一些项目,并为每个项目指定使用的能源核心,使得总价值最大,同时保证每个核心最多被一个项目使用。请你求出这个最大值。


为了防止输入过大带来的常数问题,C++ 选手请尽量使用关闭流同步的 std::cin 和 std::cout 实现输入输出,否则可能出现因读入输出问题导致的 TLE 等。

int main(){
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);

  // your code

  return 0;
}


				

输入格式

第一行一个整数 TT (1≤T≤106)(1T106),表示测试数据组数。

每组数据的第一行包含两个整数 nn 和 mm (1≤n,m≤2×105)(1n,m2×105),分别表示资源点数量和项目数量。

接下来 mm 行,每行包含三个整数 ai,bi,wiai,bi,wi (1≤ai,bi≤n,ai≠bi,1≤wi≤109)(1ai,bin,ai=bi,1wi109),分别表示项目 ii 关联的两个能源核心和项目 ii 的价值。

保证所有测试数据的 nn 之和和 mm 之和均不超过 2×1062×106

输出格式

对于每组数据,输出一行一个整数,表示最大的总价值。

输入样例 复制

3
3 7
2 1 6
1 3 7
3 1 2
1 3 2
3 2 2
1 3 7
3 2 1
4 4
3 2 10
4 3 6
1 2 1
3 4 1
5 8
5 2 8
4 3 6
5 1 10
2 5 1
2 1 4
4 5 4
5 1 1
2 5 1

输出样例 复制

20
18
32