AT_codefestival_2016_final_g Zigzag MST

[problemUrl]: https://atcoder.jp/contests/cf16-final/tasks/codefestival_2016_final_g $ 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/A

N/A

### 制約 - $ 2≦N≦200,000 $ - $ 1≦Q≦200,000 $ - $ 0≦A_i,B_i≦N-1 $ - $ 1≦C_i≦10^9 $ ### Sample Explanation 1 最小全域木は下図のようになります。 !\[\](https://atcoder.jp/img/code-festival-2016-final/f1a6c3cfd52c386e6da5c8c761a78521.png) 多重辺が存在しうることに注意して下さい。 ### Sample Explanation 2 自己ループが存在しうることに注意して下さい。