题目描述

$n$ 个点排成一行，依次从 $1$ 到 $n$ 编号。除去 $1$ 号点，每个点都有三个属性 $l_i,r_i,k_i$，满足 $k_i$ 单调递增。

若 $2\leq i< j\leq n$ 满足 $k_j-k_i\leq m$ 且 $[l_i,r_i]\cap [l_j,r_j] \not = \varnothing$，则存在一条 $i\to j$，边权为 $1$ 的边。

特殊的，若 $k_i\leq m$，还存在一条 $1\to i$，边权为 $1$ 的边。

现在请你求出 $1$ 号点到其它每个点的最短路。

输入格式

第一行两个整数 $n,m$。

接下来 $n-1$ 行，每行三个非负整数 $l_i,r_i,k_i$ 依次表示第 $2$ 号点到第 $n$ 号点的属性。

输出格式

共 $n-1$ 行，第 $i$ 行一个整数表示到第 $i+1$ 号点的最短路，不能到达则输出 -1。

3 1
1 2 1
2 3 2

1
2

数据规模与约定

对于 $30\%$ 的数据，$1\leq n\leq 2\times 10^4$；

对于 $100\%$ 的数据，$1\leq n\leq 2.5\times 10^5$，$0\leq l_i,r_i,k_i\leq 2\times 10^9$，$1\leq m\leq 2\times 10^9$，$l_i\leq r_i$。