Trong một chương trình nghệ thuật diễn ra liên tục trong n giờ. Công ty X có danh sách của \(m\) nghệ sĩ khác nhau có thể thuê để biểu diễn. Thời điểm bắt đầu biểu diễn được tính bằng 0.

Để đơn giản trong quản lí và sắp xếp, các nghệ sĩ được đánh số theo thứ tự từ 1 tới \(m\), nghệ sĩ thứ \(i\) (với \(i\ = \ 1,\ 2,\ \ldots,\ m\)) biểu diễn trong thời điểm \(s_{i}\) đến thời điểm \(t_{i}\ (0\ \leq s_{i} < t_{i} \leq n)\) với tiền công là \(c_{i}\ (0 \leq c_{i} \leq 10^{6})\)

Yêu cầu: Viết chương trình thuê các nghệ sĩ để bất cứ thời điểm nào cũng luôn có ít nhất một nghệ sĩ biểu diễn đồng thời chi phí thuê là nhỏ nhất.

Dữ liệu vào:

+ Dòng đầu tiên chứa 2 số nguyên \(n\) và \(m\ (0\ < \ n,\ m\ \leq \ 100)\)

+ \(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên không âm \(s_{i},\ t_{i}\) và \(c_{i}\).

Kết quả:

+ Một số nguyên là chi phí thuê nhỏ nhất (dữ liệu được cho đảm bảo luôn có kết quả)

Ví dụ: