题目描述

给定一个包含 $n$ 个顶点的图，顶点编号从 $0$ 到 $n-1$。初始状态下，图中没有边。

你需要处理 $q$ 个查询来添加边。在第 $i$ 个查询中（$1 \le i \le Q$），给出三个整数 $A_i, B_i$ 和 $C_i$。根据这些值，你需要按以下方式向图中添加无穷多的边：

• 添加一条权重为 $C_i$ 的无向边连接顶点 $A_i$ 和顶点 $B_i$。
• 添加一条权重为 $C_i+1$ 的无向边连接顶点 $B_i$ 和顶点 $A_i+1$。
• 添加一条权重为 $C_i+2$ 的无向边连接顶点 $A_i+1$ 和顶点 $B_i+1$。
• 添加一条权重为 $C_i+3$ 的无向边连接顶点 $B_i+1$ 和顶点 $A_i+2$。
• 添加一条权重为 $C_i+4$ 的无向边连接顶点 $A_i+2$ 和顶点 $B_i+2$。
• 添加一条权重为 $C_i+5$ 的无向边连接顶点 $B_i+2$ 和顶点 $A_i+3$。
• 添加一条权重为 $C_i+6$ 的无向边连接顶点 $A_i+3$ 和顶点 $B_i+3$。
• …

注意，顶点编号按照 $\bmod \ n$ 进行计算。例如，$n$ 表示 $0$，$2n-1$ 表示 $n-1$。

在添加完所有边之后，你需要找出包含在图的最小生成树（MST）中的边的权重之和。

输入格式

输入共 $q+1$ 行

第一行两个用空格隔开的数，分别表示 $n,q$

接下来 $q$ 行，每行三个用空格隔开的数，分别表示 $A,B,C$。

输出格式

输出如题所示。

输入输出样例 #1

输入 #1

7 1
5 2 1

输出 #1

21

输入输出样例 #2

输入 #2

2 1
0 0 1000000000

输出 #2

1000000001

输入输出样例 #3

输入 #3

5 3
0 1 10
0 2 10
0 4 10

输出 #3

42

说明

样例解释

给定图的最小生成树（MST）如下图所示。

数据范围

• 对于 $100\%$ 的数据，$2 \le N \le 2 \times 10^5, 1 \le Q \le 2 \times 10^5, 0 \le Ai, Bi \le n-1, 1 \le Ci \le 10^9$。