题目描述

给定一张 $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$。

输出格式

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

【样例解释】

第一组样例数据如下图所示，最小生成树用红色线段标出。

第二组样例数据如下图所示，最小生成树用红色线段标出。

第三组样例数据如下图所示，最小生成树用红色线段标出。

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

4
4
1000000003