Wayne 是一位城域网的管理员。他所管理的网络可以抽象为一个包含 $n$ 个顶点和 $m$ 条边的简单连通图，这意味着图中不包含任何自环，且任意两个顶点之间最多只有一条边，且至少存在一条路径。此外，该网络还满足以下条件：任意两个顶点之间最多存在两条边不相交（即不共享任何公共边）的路径。

Wayne 知道网络中每条边的带宽，但这对他来说还不够。他需要大量的统计数据来进行展示，例如，他想知道任意两个顶点之间的最大数据传输速率。为了清晰起见，顶点编号从 $1$ 到 $n$，且每条边每秒能传输的最大比特数已知。你的任务是协助他计算以下公式的值：

$$\sum_{1 \le s < t \le n} (s \oplus t \oplus \text{flow}(s, t))$$

其中 $\oplus$ 表示按位异或运算符，$\text{flow}(s, t)$ 表示顶点 $s$ 和顶点 $t$ 之间每秒能够传输的最大比特数。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。 接下来的行描述了所有测试用例。对于每个测试用例： 第一行包含两个整数 $n$ 和 $m$。 接下来的 $m$ 行，每行包含三个整数 $u, v$ 和 $w$，表示顶点 $u$ 和顶点 $v$ 之间存在一条双向边，该边在每个方向上每秒最多能传输 $w$ 比特的数据。

$1 \le T \le 100, 1 \le n \le 10^5, n - 1 \le m \le \frac{3}{2}(n - 1), 1 \le u, v \le n, u \neq v, 0 \le w < 10^9$。 保证所有测试用例中 $n$ 的总和不超过 $10^6$，且标准输入文件的大小不超过 $26$ MiB。

输出格式

对于每个测试用例，输出一行答案。

样例

输入 1

2
3 3
1 2 5
2 3 6
3 1 5
5 6
1 2 5
2 3 6
3 1 5
3 4 6
4 5 5
5 3 6

输出 1

27
116

说明

对于第一个样例，$\text{flow}(1, 2) = \text{flow}(1, 3) = 10, \text{flow}(2, 3) = 11$。