原本有一张无向带权图 $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）：没有特殊限制。