题目描述

学校新建了一条从位置 $1$ 到位置 $m$ 的长走廊。现在有 $n$ 张通行证，第 $i$ 张通行证可以在整数位置区间 $[l_i,r_i]$ 内自由通行，并有一个等级值 $w_i$。

如果选择了一些通行证，那么只要两个位置同时被至少一张已选通行证覆盖，就可以在这两个位置之间移动。通过多张区间有重叠的通行证，也可以连续移动到更远的位置。

请你从所有通行证中选出一个子集，使得能从位置 $1$ 移动到位置 $m$。一个子集的代价定义为其中最大等级值减去最小等级值。求可行子集的最小代价。

题目保证至少存在一个可行子集。

输入格式

第一行输入两个整数 $n,m$，分别表示通行证数量和终点位置。

接下来 $n$ 行，每行包含三个整数 $l_i,r_i,w_i$，表示第 $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

数据范围与约定

$1\le n\le3\cdot10^5$，$2\le m\le10^6$。

$1\le l_i<r_i\le m$，$1\le w_i\le10^6$。

保证每个测试用例至少存在一个可行的通行证子集。