原本有一张无向带权图 $G$。小艾将它放到了一个万花筒里观察，这导致 $G$ 看起来会是它旋转产生的 $n$ 个副本的并。具体来说，对于每条边 $(u,v,w)\in G$，会在 $H$ 中生成全体 $((u+i)\bmod n + 1, (v+i)\bmod n + 1, w)$ 的边。最后的图 $H$ 就是在万花筒中看到的结果。

小艾想知道这个图的最小生成树的权值和。请你帮帮她。

输入格式

本题有多组数据。第一行输入一个正整数 $T$ 表示数据组数。

对于每组数据：

• 接下来一行两个正整数 $n,m$。
• 接下来 $m$ 行每行三个正整数 $u,v,w$，表示一条边。

输出格式

输出 $T$ 行，第 $i$ 行表示第 $i$ 组询问的答案。

样例数据

样例 1 输入

2
4 2
1 3 1
1 2 2
4 2
1 3 3
1 2 1

样例 1 输出

4
3

子任务

对 $100\%$ 的数据，保证 $1\le T\le 100; 1\le n, w\le 10^9; \sum m\le 10^5$。保证生成树存在。

子任务1（30pts）：保证 $n,m\le 10$。

子任务2（20pts）：保证 $\sum n\cdot m\le 10^5$。

子任务3（20pts）：保证 $w\le 2$。

子任务4（30pts）：没有特殊限制。