题目描述

在一个数轴上有 $m$ 个点，从左到右依次编号为 $1 \sim m$。

同时有 $n$ 条可选的线段，编号从 $1$ 到 $n$，其中第 $i$ 条线段覆盖了区间 $[l_i, r_i]$ 范围内的所有的点，它有一个权值为 $w_i$。

一条线段中的点之间可以相互到达。

对于两条线段，如果它们有交集（即拥有共同覆盖的点），则我们可以从其中一条线段中的任何一个点出发到达另一条线段所覆盖的任何一个点。

你的任务是从 $n$ 条线段中选择一些线段（甚至可以把 $n$ 条线段都选择了），使其同时满足如下两个条件：

1. 这些线段能保证 $m$ 个点是连通的，这里连通的意思指的是：编号为 $1$ 的点包含在所选择的这些线段覆盖范围内，且经由这些线段能够到达编号为 $m$ 的点；
2. 所选择的这些线段权值的极差（即所选择的这些线段的权值的最大值与最小值之差）最小。

输入格式

输入的第一行包含两个整数 $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$ 条线段的相关信息。

数据保证在选择所有 $n$ 条线段的情况下这 $m$ 个点是连通的。

输出格式

输出一个整数，表示在保证 $m$ 个点是联通的情况下，所选择的线段的极差。

样例

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

3

1 10
1 10 23

0

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 30, m \le 100, w_i \le 100$
• 对于 $60\%$ 的数据，$n \le 3000, m \le 10^4, w_i \le 10^4$
• 对于 $100\%$ 的数据，$1 \le n \le 3 \cdot 10^5, 2 \le m \le 10^6, 1 \le l_i \lt r_i \le m, 1 \le w_i \le 10^6$