配点 : $1300$ 点

問題文

$N$ 個の頂点からなるグラフがあり、頂点には $0 \sim N-1$ の番号が付けられています。辺はまだありません。

辺を追加するクエリを $Q$ 個処理します。 $i (1 \leq i \leq Q)$ 番目のクエリでは $A_i, B_i, C_i$ の $3$ つの整数が与えられるので、以下のように辺を無限本追加します。

• $A_i$ 番の頂点と $B_i$ 番の頂点をつなぐ、重み $C_i$ の無向辺を追加する。
• $B_i$ 番の頂点と $A_i+1$ 番の頂点をつなぐ、重み $C_i+1$ の無向辺を追加する。
• $A_i+1$ 番の頂点と $B_i+1$ 番の頂点をつなぐ、重み $C_i+2$ の無向辺を追加する。
• $B_i+1$ 番の頂点と $A_i+2$ 番の頂点をつなぐ、重み $C_i+3$ の無向辺を追加する。
• $A_i+2$ 番の頂点と $B_i+2$ 番の頂点をつなぐ、重み $C_i+4$ の無向辺を追加する。
• $B_i+2$ 番の頂点と $A_i+3$ 番の頂点をつなぐ、重み $C_i+5$ の無向辺を追加する。
• $A_i+3$ 番の頂点と $B_i+3$ 番の頂点をつなぐ、重み $C_i+6$ の無向辺を追加する。
• ...

ただし、頂点番号は mod $N$ で考えます。 たとえば、$N$ 番とは $0$ 番のことであり、$2N-1$ 番とは $N-1$ 番のことです。

例えば、$N=16, A_i=7, B_i=14, C_i=1$ のときは下図のように辺を追加します。（図では最初の $7$ 本のみ）

すべての辺を追加した後のグラフの最小全域木に含まれる辺の重みの和を求めて下さい。

制約

• $2 \leq N \leq 200,000$
• $1 \leq Q \leq 200,000$
• $0 \leq A_i,B_i \leq N-1$
• $1 \leq C_i \leq 10^9$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $Q$

$A_1$ $B_1$ $C_1$

$A_2$ $B_2$ $C_2$

:

$A_Q$ $B_Q$ $C_Q$

出力

最小全域木に含まれる辺の重みの和を出力せよ。

7 1
5 2 1

21

最小全域木は下図のようになります。

多重辺が存在しうることに注意して下さい。

2 1
0 0 1000000000

1000000001

自己ループが存在しうることに注意して下さい。

5 3
0 1 10
0 2 10
0 4 10

42