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$。

每组数据输出一行一个整数，表示这张图的最小生成树的边权之和。

**【样例解释】** 第一组样例数据如下图所示，最小生成树用红色线段标出。  第二组样例数据如下图所示，最小生成树用红色线段标出。  第三组样例数据如下图所示，最小生成树用红色线段标出。