← 返回题目列表

AtCoder · codefestival_2016_final_g

G. 之字形 MST

中文机器翻译题面 查看原题

分数: 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