Thư viện Khoa học Tổng hợp Đà Nẵng phối hợp với Hội Nhà Báo TP. Đà Nẵng và CLB Nhiếp ảnh TP. Đà Nẵng tổ chức Hội Báo Xuân Giáp Thìn năm 2024, triển lãm tài nguyên thông tin và các tác phẩm nhiếp ảnh nghệ thuật chào Xuân. Những tác phẩm nhiếp ảnh nghệ thuật thường là mục tiêu của nhiều tổ chức trộm căp chuyên nghiệp. Vì thế, ban tổ chức cần giải quyết bài toán bảo vệ an toàn cho các tác phẩm này. Theo kế hoạch, các tác phẩm được trưng bày trong ~n~ giờ, thời điểm bắt đầu cuộc triển lãm được tính bằng ~0~. Có ~m~ vệ sĩ nghiệp vụ cao có thể thuê để canh gác các tác phẩm. Để đơn giản, các vệ sĩ này được đánh số thứ tự từ ~1~ đến ~m~. Vệ sĩ ~i~ chấp nhận đứng canh trong khoản thời gian từ ~s_i~ đến thời điểm ~t_i(0 \le s_i < t_i \le n)~ với tiền công là ~c_i~ (với ~i = 1, 2, ..., n~)

Yêu cầu

Hãy giúp ban tổ chức lựa chọn thuê các vệ sĩ nào trong số ~m~ vệ sĩ để bất cứ thời điểm nào diễn ra triển lãm luôn có ít nhất một vệ sĩ đứng canh, đồng thời tổng chi phí thuê trả cho các vệ sĩ đó là nhỏ nhất

Input

Đọc từ tệp văn bản HBAOXUAN.INP có cấu trúc như sau

• Dòng đầu ghi hai số nguyên dương ~n~ và ~m(1 \le n, m \le 10^5)~
• Dòng thứ ~i~ trong ~m~ tiếp theo chứa ba số nguyên không âm ~s_i, t_i, c_i(0 \le c_i \le 10^5)~

Các số trên một dòng các nhau bởi một khoản trắng. Dữ liệu luôn đảm bảo có lời giải.

Output

Ghi ra tệp văn bản HBAOXUAN.OUT một số nguyên duy nhất là tổng chi phí nhỏ nhất để thuê các vệ sĩ

Ví dụ

HBAOXUAN.INP

9 5
0 5 25
1 3 18
3 7 21
4 6 38
7 9 20

HBAOXUAN.OUT

66

Giải thích

Lựa chọn ba vệ sĩ có số thứ tự lần lượt là 1, 3, 5.
Tổng chi phí sử dụng để trả cho 3 vệ sĩ này là 25 + 21 + 20 = 66

Ràng buộc

• Có ~50~% số test đầu với ~1 \le n, m \le 10^3~
• Có ~50~% số test còn lại không giới hạn gì thêm