P9701 [GDCPC 2023] Classic Problem

给定一张 $n$ 个点的无向完全图与 $m$ 个三元组 $P_1, P_2, \cdots, P_m$，其中 $P_i = (u_i, v_i, w_i)$。保证 $1 \leq u_i < v_i \leq n$，且对于任意两个编号不同的三元组 $P_i$ 和 $P_j$，有 $(u_i, v_i) \ne (u_j, v_j)$。 对于图中的任意两个节点 $x$ 与 $y$（$1 \leq x < y \leq n$），定义它们之间的无向边的边权如下： - 如果存在一个三元组 $P_i$ 满足 $u_i = x$ 且 $v_i = y$，那么边权为 $w_i$。 - 否则，边权为 $|x - y|$。 求这张图的最小生成树的边权之和。

有多组测试数据。第一行输入一个整数 $T$（$1 \le T \le 10^5$）表示测试数据组数。对于每组测试数据： 第一行输入两个整数 $n$ 和 $m$（$1 \leq n \leq 10^9$，$0 \leq m \leq 10^5$）表示图的点数与三元组的数量。 对于接下来 $m$ 行，第 $i$ 行输入三个整数 $u_i$，$v_i$ 和 $w_i$（$1 \leq u_i < v_i \leq n$，$0 \leq w_i \leq 10^9$）表示第 $i$ 个三元组。保证对于所有 $1 \leq i < j \leq m$ 都有 $(u_i, v_i) \ne (u_j, v_j)$。 保证所有数据 $m$ 之和不超过 $5 \times 10^5$。

每组数据输出一行一个整数，表示这张图的最小生成树的边权之和。 **【样例解释】** 第一组样例数据如下图所示，最小生成树用红色线段标出。  第二组样例数据如下图所示，最小生成树用红色线段标出。  第三组样例数据如下图所示，最小生成树用红色线段标出。 

The first sample test case is illustrated as follows. The minimum spanning tree is marked by red segments.  The second sample test case is illustrated as follows. The minimum spanning tree is marked by red segments.  The third sample test case is illustrated as follows. The minimum spanning tree is marked by red segments.