分数: 1300 点
问题陈述
我们有一个图表 N 顶点,编号 0 通过 N-1。边缘尚未添加。
我们将处理 Q 查询以添加边。 在 i-th (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