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).

Yêu cầu: 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 200,000; 1 \le M \le 100,000~);
• ~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~).

Output

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