Cho một đồ thị với ~ N ~ đỉnh, được đánh số từ ~ 0 ~ đến ~ N-1 ~. Ban đầu, các cạnh vẫn chưa được thêm vào.

Chúng ta cần xử lý ~ Q ~ truy vấn để thêm các cạnh. Trong truy vấn thứ ~ i ~ ~(1 ≤ i ≤ Q) ~, cho ba số nguyên ~ A_i, B_i ~ và ~ C_i ~ và chúng ta sẽ thêm vô số cạnh vào biểu đồ như sau:

• Hai đỉnh được đánh số ~ A_i ~ và ~ B_i ~ sẽ được nối với nhau bằng một cạnh có trọng số là ~ C_i ~.
• Hai đỉnh được đánh số ~ B_i ~ và ~ A_i + 1 ~ sẽ được nối với nhau bằng một cạnh có trọng số ~ C_i + 1 ~.
• Hai đỉnh được đánh số ~ A_i + 1 ~ và ~ B_i + 1 ~ sẽ được nối với nhau bởi một cạnh có trọng số ~ C_i + 2 ~.
• Hai đỉnh được đánh số ~ B_i + 1 ~ và ~ A_i + 2 ~ sẽ được nối với nhau bằng một cạnh có trọng số ~ C_i + 3 ~.
• Hai đỉnh được đánh số ~ A_i + 2 ~ và ~ B_i + 2 ~ sẽ được nối với nhau bởi một cạnh có trọng số ~ C_i + 4 ~.
• Hai đỉnh được đánh số ~ B_i + 2 ~ và ~ A_i + 3 ~ sẽ được nối với nhau bằng một cạnh có trọng số ~ C_i + 5 ~.
• Hai đỉnh được đánh số ~ A_i + 3 ~ và ~ B_i + 3 ~ sẽ được nối với nhau bằng một cạnh có trọng số ~ C_i + 6 ~.
• ...

Ở đây, hãy xem xét các chỉ số của các đỉnh modulo ~ N ~. Ví dụ, đỉnh được đánh số ~ N ~ là một được đánh số ~ 0 ~, và đỉnh được đánh số ~ 2N-1 ~ là một được đánh số ~ N-1 ~.

Hình dưới đây cho thấy bảy cạnh đầu tiên được thêm vào khi ~ N = 16, A_i = 7, B_i = 14, C_i = 1 ~:

Sau khi xử lý tất cả các truy vấn, bạn hãy tìm tổng trọng số của các cạnh có trong cây khung nhỏ nhất của đồ thị.

Lưu ý rằng có thể có nhiều cạnh nối cùng một cặp đỉnh.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~Q~ (~2 ≤ N ≤ 2 * 10^5, 1 ≤ Q ≤ 2 * 10^5~).
• ~Q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~A_i~ ~B_i~ ~C_i~ (~0 ≤ A_i, B_i ≤ N-1, 1 ≤ C_i ≤ 10 ^ 9~).

Output

In tổng trọng số của các cạnh có trong cây khung nhỏ nhất của đồ thị.

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

Giải thích

Trong testcase 1, hình dưới đây cho thấy cây khung nhỏ nhất của đồ thị: