Có ~n~ bóng đèn được đặt tại các vị trí từ ~1~ đến ~n~. Ban đầu, tất cả các bóng đèn đều đang tắt.

Có ~q~ thao tác. Thao tác thứ ~i~ được mô tả bởi ba số nguyên ~l_i, r_i, A_i~. Nếu thực hiện thao tác này, trạng thái của mọi bóng đèn tại các vị trí từ ~l_i~ đến ~r_i~ sẽ bị đảo:

• bóng đang tắt sẽ chuyển thành bật;
• bóng đang bật sẽ chuyển thành tắt.

Chi phí để thực hiện thao tác thứ ~i~ là ~A_i~.

Mỗi thao tác có thể được thực hiện không quá một lần.

Hãy chọn một số thao tác sao cho sau khi thực hiện xong, tất cả ~n~ bóng đèn đều bật, đồng thời tổng chi phí là nhỏ nhất.

Dữ liệu bảo đảm luôn tồn tại ít nhất một cách thực hiện thỏa mãn yêu cầu.

Input

• Dòng đầu gồm hai số nguyên ~n, q~.
• ~q~ dòng tiếp theo, dòng thứ ~i~ gồm ba số nguyên ~l_i, r_i, A_i~, mô tả thao tác thứ ~i~.

Output

In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất để bật toàn bộ ~n~ bóng đèn.

Ràng buộc

• ~1 \le n, q \le 10^5~
• ~1 \le l_i \le r_i \le n~
• ~1 \le A_i \le 10^9~
• Luôn tồn tại ít nhất một cách chọn các thao tác để tất cả bóng đèn đều bật.

Ví dụ

Input

5 4
1 2 3
3 5 4
1 5 10
2 4 100

Output

7

Giải thích

Chọn hai thao tác ~[1,2]~ và ~[3,5]~.

Sau khi thực hiện hai thao tác này, tất cả các bóng đèn từ ~1~ đến ~5~ đều bật.

Tổng chi phí là ~3+4=7~, và đây là chi phí nhỏ nhất.