Ở Cộng hòa JOI có \(N\) nhà ga, được đánh số từ \(1\) đến \(N\) và nằm theo thứ tự chiều kim đồng hồ trên một tuyến đường sắt hình tròn.

Có \(N\) loại vé tàu, được đánh số từ \(1\) đến \(N\). Một vé loại \(i\) với \(1 \le i \le N-1\) cho phép một người đi từ ga \(i\) đến ga \(i+1\) hoặc theo chiều ngược lại. Một vé loại \(N\) cho phép một người đi giữa ga \(1\) và ga \(N\) theo một trong hai chiều. Vé chỉ được bán theo gói gồm đúng \(N\) vé, mỗi loại một vé.

Bạn làm việc tại một đại lý du lịch và hôm nay nhận được \(M\) yêu cầu. Yêu cầu thứ \(i\) cho biết có \(C_i\) người muốn đi từ ga \(A_i\) đến ga \(B_i\). Những người thuộc cùng một yêu cầu không nhất thiết phải đi cùng tuyến đường.

Yêu cầu

Tính số gói vé ít nhất cần mua để đáp ứng tất cả các yêu cầu.

Dữ liệu vào

• Dòng đầu gồm hai số nguyên \(N,M\), là số nhà ga và số yêu cầu.
• Trong \(M\) dòng tiếp theo, dòng thứ \(i\) gồm ba số nguyên \(A_i,B_i,C_i\), cho biết có \(C_i\) người muốn đi từ ga \(A_i\) đến ga \(B_i\).

Dữ liệu ra

In ra số gói vé ít nhất cần mua.

Ràng buộc

• \(3 \le N \le 200\,000\).
• \(1 \le M \le 100\,000\).
• \(1 \le A_i,B_i \le N\) với mọi \(1 \le i \le M\).
• \(1 \le C_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le M\).
• \(A_i \ne B_i\) với mọi \(1 \le i \le M\).

Phân nhóm

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

Giới hạn

• Thời gian: 4 giây.
• Bộ nhớ: 256 MB.

Ví dụ

3 3
1 2 1
2 3 1
3 1 1

1

3 2
1 2 4
1 2 2

3

6 3
1 4 1
2 5 1
3 6 1

2