Problem Description

There is a graph with $ N $ vertices, numbered from $ 0 $ to $ N-1 $. There are no edges initially.

We will process $ Q $ queries to add edges. In the $i\ (1≦i≦Q)$ -th query, three integers $ A_i, B_i, C_i $ are given, and we will add an infinite number of edges as follows:

• Add an undirected edge with weight $ C_i $ between vertex $ A_i $ and vertex $ B_i $.
• Add an undirected edge with weight $ C_i+1 $ between vertex $ B_i $ and vertex $ A_i+1 $.
• Add an undirected edge with weight $ C_i+2 $ between vertex $ A_i+1 $ and vertex $ B_i+1 $.
• Add an undirected edge with weight $ C_i+3 $ between vertex $ B_i+1 $ and vertex $ A_i+2 $.
• Add an undirected edge with weight $ C_i+4 $ between vertex $ A_i+2 $ and vertex $ B_i+2 $.
• Add an undirected edge with weight $ C_i+5 $ between vertex $ B_i+2 $ and vertex $ A_i+3 $.
• Add an undirected edge with weight $ C_i+6 $ between vertex $ A_i+3 $ and vertex $ B_i+3 $.
• ...

Note that vertex numbers are considered modulo $ N $. For example, vertex $ N $ is the same as vertex $ 0 $, and vertex $ 2N-1 $ is the same as vertex $ N-1 $.

For example, when $ N=16, A_i=7, B_i=14, C_i=1 $, edges are added as shown in the figure below (only the first 7 edges are shown).

After adding all the edges, find the sum of the weights of the edges included in the minimum spanning tree of the graph.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the sum of the weights of the edges included in the minimum spanning tree.

Sample Input and Output

Sample Input #1

7 1
5 2 1

Sample Output #1

21

Sample Input #2

2 1
0 0 1000000000

Sample Output #2

1000000001

Sample Input #3

5 3
0 1 10
0 2 10
0 4 10

Sample Output #3

42

Notes/Hints

Constraints

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

Sample Explanation 1

The minimum spanning tree is as shown in the figure below.  Note that multiple edges may exist.

Sample Explanation 2

Note that self-loops may exist.

见题面 Input 部分

见题面 Output 部分