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 Gíap 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 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 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ĩ có thể thuê để canh gác tác phẩm. Để đơn giản, các vệ sĩ này được đánh số từ \(1\) đến \(m\). Vệ sĩ \(i\) chấp nhận đứng canh trong khoảng thời gian từ thời điểm \(s_i\) đến thời điểm \(t_i\) (\(0 \le s_i \le t_i \le n\)) với tiền công là \(c_i\) (với \(i=1, 2, \dots, m\)).

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 \(1\) 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 tiên ghi hai số nguyên dương \(n\) và \(m\) (\(1 \le n \le m \le 10^5\));
  • Dòng thứ \(i\) trong \(m\) dòng tiếp theo chứa ba số nguyên không âm \(s_i, t_i, c_i\) (\(0 \le c_i \le 10^9\)). Các số trên một dòng cách nhau bởi một khoảng trắng. Dữ liệu đảm bảo luôn 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ĩ.

Scoring

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

Example

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

66