题目描述

Given an undirected complete graph with $n$ vertices and $m$ triples $P_1, P_2, \cdots, P_m$ where $P_i = (u_i, v_i, w_i)$, it's guaranteed that $1 \leq u_i < v_i \leq n$, and for any two triples $P_i$ and $P_j$ with different indices we have $(u_i, v_i) \ne (u_j, v_j)$.

For any two vertices $x$ and $y$ in the graph ($1 \leq x < y \leq n$), define the weight of the edge connecting them as follows:

• If there exists a triple $P_i$ satisfying $u_i = x$ and $v_i = y$, the weight of edge will be $w_i$.
• Otherwise, the weight of edge will be $|x - y|$.

Calculate the total weight of edges in the minimum spanning tree of the graph.

输入格式

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^5$) indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($1 \leq n \leq 10^9$, $0 \leq m \leq 10^5$) indicating the number of vertices in the graph and the number of triples.

For the following $m$ lines, the $i$-th line contains three integers $u_i$, $v_i$ and $w_i$ ($1 \leq u_i < v_i \leq n$, $0 \leq w_i \leq 10^9$) indicating the $i$-th triple. It's guaranteed that for all $1 \leq i < j \leq m$ we have $(u_i, v_i) \ne (u_j, v_j)$.

It's guaranteed that the sum of $m$ of all test cases will not exceed $5 \times 10^5$.

输出格式

For each test case output one line containing one integer indicating the total weight of edges in the minimum spanning tree of the graph.

题目大意

【题目描述】

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

提示

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.