CF1555E Boring Segments

给定数轴上的 $n$ 个线段，编号为 $1$ 到 $n$。第 $i$ 个线段覆盖所有从 $l_i$ 到 $r_i$ 的整数点，并且有一个权值 $w_i$。 你需要选择这些线段的一个子集（可以是全部）。一旦选定了子集，如果存在一个被选中的线段同时覆盖两个整数点，则可以在这两个点之间移动。若从点 $1$ 出发，经过任意多次移动可以到达点 $m$，则称该子集为“好子集”。 该子集的代价定义为其中最大权值与最小权值之差。请你求出一个好子集的最小代价。 保证每组测试数据至少存在一个好子集。

第一行包含两个整数 $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$ 个线段。 保证每组测试数据至少存在一个好子集。

输出一个整数，表示一个好子集的最小代价。

由 ChatGPT 4.1 翻译