もともと無向重み付きグラフ $G$ があった。小艾（Xiao Ai）はそれを万華鏡に入れて観察した。その結果、$G$ は回転によって生成される $n$ 個のコピーの和集合として見えるようになった。具体的には、$G$ の各辺 $(u,v,w)$ に対して、$H$ にはすべての $((u+i)\bmod n + 1, (v+i)\bmod n + 1, w)$ という辺が生成される。最終的なグラフ $H$ が万華鏡の中で見える結果である。

小艾はこのグラフの最小全域木の重みの総和を知りたい。彼女を助けてあげてほしい。

入力

この問題は複数のテストケースを含む。最初の行にテストケースの数を示す正整数 $T$ が入力される。

各テストケースについて：

• 次の行に2つの正整数 $n, m$ が与えられる。
• 続く $m$ 行のそれぞれに、辺を表す3つの正整数 $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

小課題

すべてのデータにおいて、$1\le T\le 100; 1\le n, w\le 10^9; \sum m\le 10^5$ を満たす。全域木が存在することは保証される。

小課題1（30点）：$n, m\le 10$ を満たす。

小課題2（20点）：$\sum n\cdot m\le 10^5$ を満たす。

小課題3（20点）：$w\le 2$ を満たす。

小課題4（30点）：特別な制限はない。