Đoạn nhàm chán

Cho $n$ đoạn thẳng trên trục số, đánh số từ $1$ đến $n$. Đoạn thứ $i$ phủ mọi điểm nguyên từ $l_i$ đến $r_i$ và có giá trị $w_i$.

Bạn cần chọn ra một tập con của các đoạn này (có thể chọn tất cả). Sau khi đã chọn tập con, ta có thể di chuyển giữa hai điểm nguyên nếu tồn tại một đoạn đã chọn phủ cả hai điểm đó. Một tập con được gọi là tốt nếu xuất phát từ điểm $1$ ta có thể đến được điểm $m$ sau một số bước di chuyển tùy ý.

Chi phí của một tập con là hiệu giữa giá trị lớn nhất và giá trị nhỏ nhất của các đoạn trong tập đó. Hãy tìm chi phí nhỏ nhất của một tập con tốt.

Dữ liệu luôn đảm bảo tồn tại ít nhất một tập con tốt.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• $n$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $l_i$, $r_i$ và $w_i$: mô tả đoạn thứ $i$.

Dữ liệu ra

• In ra một số nguyên duy nhất: chi phí nhỏ nhất của một tập con tốt.

Ràng buộc

• $1\le n\le 3·{10}^5$
• $2\le m\le {10}^6$
• $1\le l_i<r_i\le m$
• $1\le w_i\le {10}^6$
• Dữ liệu luôn có ít nhất một tập con tốt.

Ví dụ