E. Скучные отрезки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны $$$n$$$ отрезков на числовой прямой, отрезки пронумерованы от $$$1$$$ до $$$n$$$. $$$i$$$-й отрезок покрывает все целочисленные точки от $$$l_i$$$ до $$$r_i$$$ и имеет значение $$$w_i$$$.

Требуется выбрать поднабор этих отрезков (возможно, все). Когда набор выбран, разрешается перемещаться между двумя целочисленными точками, если существует выбранный отрезок, который накрывает обе точки. Поднабор называется хорошим, если возможно достичь точку $$$m$$$, начав из точки $$$1$$$, за произвольное количество ходов.

Цена поднабора — это разность между максимальным и минимальным значениями отрезков в нем. Найдите минимальную цену хорошего поднабора.

В каждом тесте существует хотя бы один хороший набор.

Входные данные

В первой строке записаны два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5$$$; $$$2 \le m \le 10^6$$$) — количество отрезков и количество целочисленных точек.

В каждой из следующих $$$n$$$ строк записаны по три целых числа $$$l_i$$$, $$$r_i$$$ и $$$w_i$$$ ($$$1 \le l_i < r_i \le m$$$; $$$1 \le w_i \le 10^6$$$) — описание $$$i$$$-го отрезка.

В каждом тесте существует хотя бы один хороший набор.

Выходные данные

Выведите одно целое число — минимальную цену хорошего поднабора.

Примеры
Входные данные
5 12
1 5 5
3 4 10
4 10 6
11 12 5
10 12 3
Выходные данные
3
Входные данные
1 10
1 10 23
Выходные данные
0