题目描述

给定数轴上的 $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$ 个线段。

保证每组测试数据至少存在一个好子集。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

3

输入输出样例 #2

输入 #2

1 10
1 10 23

输出 #2

0

说明/提示

对于样例1，我们可以选择1、3、5号区间，最大和最小值的差为3