Boring Segments

题意翻译

在一个 $[1,m]$ 的数轴上有 n 条线段，第 i 条覆盖了 $[l_i,r_i]$ 的区间，权值为 $w_i$ ，你的任务是从这些线段中选出若干条首尾相接线段覆盖整个数轴，使得这些线段权值极差最小化，输出这个极差 首尾相接的定义是，假设你有机会从同一条线段覆盖的任意两个点中移动，如果你可以从位置 1 出发，经过一些线段到达位置 m ，就称为这些线段首尾相接

题目描述

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.

输入输出格式

输入格式

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 < 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.

输出格式

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

输入输出样例

输入样例 #1

5 12
1 5 5
3 4 10
4 10 6
11 12 5
10 12 3

输出样例 #1

3

输入样例 #2

1 10
1 10 23

输出样例 #2

0

题意翻译

在一个 $[1,m]$ 的数轴上有 n 条线段，第 i 条覆盖了 $[l_i,r_i]$ 的区间，权值为 $w_i$ ，你的任务是从这些线段中选出若干条首尾相接线段覆盖整个数轴，使得这些线段权值极差最小化，输出这个极差 首尾相接的定义是，假设你有机会从同一条线段覆盖的任意两个点中移动，如果你可以从位置 1 出发，经过一些线段到达位置 m ，就称为这些线段首尾相接