题目描述

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

辺を追加するクエリを $Q$ 個処理します。 $i\ (1≦i≦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$ 本のみ）

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

输入格式

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

$N$ $Q$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ : $A_Q$ $B_Q$ $C_Q$

输出格式

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

题目大意

对一张 n 个点的图做Q次加边操作，每次给定 Ai, Bi, Ci，然后按顺序连边(Ai,Bi,Ci),(Bi,Ai+1,Ci+1),(Ai+1,Bi+1,Ci+2)等等，求给定图的最小生成树。（Ai，Bi，Ci等点编号均为对n取模的意义下） 给定 初始的n,q,Ai,Bi,Ci； （2≦N≦200,000）（1≦Q≦200,000） （0≦Ai,Bi≦N−1）（1≦Ci≦10^9）

7 1
5 2 1

21

2 1
0 0 1000000000

1000000001

5 3
0 1 10
0 2 10
0 4 10

42

提示

制約

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

Sample Explanation 1

最小全域木は下図のようになります。  多重辺が存在しうることに注意して下さい。

Sample Explanation 2

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