Hội báo xuân

Thư viện Khoa học Tổng hợp Đà Nẵng phối hợp với Hội Nhà báo thành phố và CLB Nhiếp ảnh tổ chức Hội Báo Xuân Giáp Thìn năm 2024, triển lãm ảnh nghệ thuật, tuyên truyề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 những kẻ 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ảng thời gian từ thời điểm \(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, \ldots, 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 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

• 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\) 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^5\)).
  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.

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.

Output

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

Example

Input:

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

Output:

66

Note

Lựa chọn ba vệ sĩ có số thứ tự lần lượt là \(1, 3, 5\). Họ canh trong các khoảng \([0,5]\), \([3,7]\), \([7,9]\) phủ kín toàn bộ thời gian từ \(0\) đến \(9\). Tổng chi phí sử dụng để trả cho \(3\) vệ sĩ này là \(25+21+20=66\).