CF1555E.Boring Segments

You are given $n$ segments on a number line, numbered from $1$ to $n$. The $i$-th segments covers all integer points from $l_i$ to $r_i$ and has a value $w_i$.

You are asked to select a subset of these segments (possibly, all of them). Once the subset is selected, it's possible to travel between two integer points if there exists a selected segment that covers both of them. A subset is good if it's possible to reach point $m$ starting from point $1$ in arbitrary number of moves.

The cost of the subset is the difference between the maximum and the minimum values of segments in it. Find the minimum cost of a good subset.

In every test there exists at least one good subset.

给你数轴上的 $n$ 条线段，编号从 $1$ 到 $n$。第 $i$ 条线段覆盖所有从 $l_i$ 到 $r_i$ 的整数点，并具有权值 $w_i$。

你需要从中选出一个子集（可以包含全部线段）。选定子集后，若存在一条被选中的线段同时覆盖两个整数点，则可以从其中一个点移动到另一个点。若能从点 $1$ 出发，经过任意次移动到达点 $m$，则称该子集是“好的”。

该子集的代价定义为其中所含线段权值的最大值与最小值之差。请找出一个“好”子集的最小可能代价。

每个测试用例中至少存在一个“好”子集。

The first line contains two integers $n$ and $m$ ($1 \le n \le 3 \cdot 10^5$; $2 \le m \le 10^6$) — the number of segments and the number of integer points.

Each of the next $n$ lines contains three integers $l_i$, $r_i$ and $w_i$ ($1 \le l_i \lt r_i \le m$; $1 \le w_i \le 10^6$) — the description of the $i$-th segment.

In every test there exists at least one good subset.

第一行包含两个整数 $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 \lt r_i \le m$；$1 \le w_i \le 10^6$）—— 描述第 $i$ 条线段。

在每个测试用例中，至少存在一个“好”的子集。

Print a single integer — the minimum cost of a good subset.

输出一个整数——优质子集的最小代价。