#P18688. Classic Problem
Classic Problem
Classic Problem
给定一张有 个顶点的无向完全图,以及 个三元组 ,其中 。保证 ,且任意两个不同三元组的端点对 不同。
对于任意两个顶点 (),连接它们的边权按以下规则确定:
- 如果存在三元组 满足 ,则这条边的权值为 ;
- 否则,这条边的权值为 。
求这张图的最小生成树的边权总和。
输入格式
第一行包含整数 (),表示测试用例数。
对于每个测试用例,第一行包含两个整数 (,),分别表示顶点数和三元组数。
接下来 行,第 行包含三个整数 (,),表示第 个三元组。保证这些三元组的端点对互不相同。
保证整个输入中所有测试用例的 之和不超过 。
输出格式
对于每个测试用例,输出一行,包含一个整数,表示最小生成树的边权总和。
样例 1 输入
3
5 3
1 2 5
2 3 4
1 5 0
5 0
5 4
1 2 1000000000
1 3 1000000000
1 4 1000000000
1 5 1000000000
样例 1 输出
4
4
1000000003
样例说明
第一组测试用例如下图所示,红色线段组成一棵最小生成树。

第二组测试用例如下图所示,红色线段组成一棵最小生成树。

第三组测试用例如下图所示,红色线段组成一棵最小生成树。
