Trên tuyến đường sắt nọ có \(N\) ga, được đánh số từ \(1\) đến \(N\) theo chiều kim đồng hồ.

Có \(N\) loại vé cho tuyến đường sắt này, mỗi loại được đánh số từ \(1\) đến \(N\). Vé loại \(i\) (\(1 \le i \le N - 1\)) chỉ dành cho một người di chuyển theo chiều kim đồng hồ từ ga \(i\) đến ga \(i + 1\) hoặc cho một người di chuyển ngược chiều kim đồng hồ từ ga \(i + 1\) đến ga \(i\). Vé \(N\) chỉ dành cho một người di chuyển theo chiều kim đồng hồ từ ga \(N\) đến ga \(1\) hoặc cho một người di chuyển ngược chiều kim đồng hồ từ ga \(1\) đến ga \(N\).

Chỉ có một cách mua vé: mua trọn gói, mỗi gói gồm các vé \(1, 2, \dots, N\). Bạn là hướng dẫn viên du lịch và bạn đang đặt vé cho khách du lịch. Có \(M\) yêu cầu bán vé. Yêu cầu bán vé \(i\) (\(1 \le i \le M\)) mô tả có \(C_i\) hành khách muốn đi từ ga \(A_i\) đến ga \(B_i\) (các tuyến đường có thể khác nhau).

Hãy tính xem cần phải mua tối thiểu là bao nhiêu gói vé.

Input

• Dòng 1: chứa hai số nguyên \(N, M\) (\(1 \le N \le 2 \cdot 10^5; 1 \le M \le 10^5\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(A_i, B_i, C_i\) (\(1 \le A_i, B_i \le N; C_i \le 10^9\) với mọi \(i = 1 \dots M\)).

Output

• Một số nguyên duy nhất là số gói tối thiểu cần mua.

Example

3 3
2 3 1
1 2 1
3 1 1

1

3 2
1 2 2
1 2 4

3

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(1 \le N, M \le 20; C_i = 1\) với mọi \(i = 1 \dots M\).
• Subtask \(2\) (\(35\%\) số điểm): \(1 \le N, M \le 300; C_i = 1\) với mọi \(i = 1 \dots M\).
• Subtask \(3\) (\(20\%\) số điểm): \(1 \le N, M \le 3000; C_i = 1\) với mọi \(i = 1 \dots M\).
• Subtask \(4\) (\(20\%\) số điểm): \(1 \le N \le 2 \cdot 10^5; 1 \le M \le 10^5; C_i = 1\) với mọi \(i = 1 \dots M\).
• Subtask \(5\) (\(15\%\) số điểm): Không có ràng buộc bổ sung.