题目描述

我们有一个具有$N$个顶点的图，编号为$0$到$N-1$。边还没有添加。

我们将处理$Q$个查询来添加边。在第$i$个$(1≤i≤Q)$查询中，将给出三个整数$A_i, B_i$和$C_i$，我们将如下无限添加多条边到图中：

• 编号为$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$相连。
• ...

在这里，考虑顶点的索引对$N$取模。例如，编号为$N$的顶点是编号为$0$的顶点，编号为$2N-1$的顶点是编号为$N-1$的顶点。

下图显示了当$N=16, A_i=7, B_i=14, C_i=1$时添加的前七条边：

处理完所有查询后，找到包含在图的最小生成树中的边的总权重。

约束条件

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

输入

输入以以下格式从标准输入给出：

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

输出

打印包含在图的最小生成树中的边的总权重。

示例输入 1

7 1
5 2 1

示例输出 1

21

下图显示了图的最小生成树：

注意，可以有多条连接相同一对顶点的边。

示例输入 2

2 1
0 0 1000000000

示例输出 2

1000000001

还要注意，可以有自环。

示例输入 3

5 3
0 1 10
0 2 10
0 4 10

示例输出 3

42