Description

给定一张 \(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|\)。

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

Input

有多组测试数据。第一行输入一个整数 \(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\)。

Output

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

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

Hint

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

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

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