#P18688. Classic Problem

    ID: 18024 传统题 8000ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600提高+/省选-BorůvkaKruskal有限候选集缩减离散化普通并查集有序集合二分查找

Classic Problem

Classic Problem

给定一张有 nn 个顶点的无向完全图,以及 mm 个三元组 P1,P2,…,PmP_1,P_2,\ldots,P_m,其中 Pi=(ui,vi,wi)P_i=(u_i,v_i,w_i)。保证 1≤ui<vi≤n1\le u_i<v_i\le n,且任意两个不同三元组的端点对 (ui,vi)(u_i,v_i) 不同。

对于任意两个顶点 x,yx,y(1≤x<y≤n1\le x<y\le n),连接它们的边权按以下规则确定:

  • 如果存在三元组 PiP_i 满足 ui=x,vi=yu_i=x,v_i=y,则这条边的权值为 wiw_i;
  • 否则,这条边的权值为 ∣x−y∣|x-y|。

求这张图的最小生成树的边权总和。

输入格式

第一行包含整数 TT(1≤T≤1051\le T\le10^5),表示测试用例数。

对于每个测试用例,第一行包含两个整数 n,mn,m(1≤n≤1091\le n\le10^9,0≤m≤1050\le m\le10^5),分别表示顶点数和三元组数。

接下来 mm 行,第 ii 行包含三个整数 ui,vi,wiu_i,v_i,w_i(1≤ui<vi≤n1\le u_i<v_i\le n,0≤wi≤1090\le w_i\le10^9),表示第 ii 个三元组。保证这些三元组的端点对互不相同。

保证整个输入中所有测试用例的 mm 之和不超过 5×1055\times10^5。

输出格式

对于每个测试用例,输出一行,包含一个整数,表示最小生成树的边权总和。

样例 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

样例说明

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

第一组测试用例原图

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

第二组测试用例原图

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

第三组测试用例原图