题目描述

大 sz 最近在玩一个由星球大战改编的游戏。话说绝地武士当前共控制了 $n$ 个星球。但是，西斯正在暗处悄悄地准备他们的复仇计划。绝地评议会也感觉到了这件事。于是，准备加派绝地武士到各星球防止西斯的突袭。一个星球受到攻击以后，会尽快通知到总基地。需要的时间越长的星球就需要越多绝地武士来防御。为了合理分配有限的武士，大 sz 需要你帮他求出每个星球各需要多少时间能够通知到总基地。由于某种原因，$n$ 个星球排成一条直线，编号 $1$ 至 $n$。其中总基地建在 $1$ 号星球上。每个星球虽然都是绝地武士控制的，但是上面居住的生物不一定相同，并且科技水平也不一样。第 $i$ 个星球能收到并分析波长在 $[x_i, y_i]$ 之间的信号，并且也能够发出在这个区间的信号，但是不能发出其他任何波长的信号。由于技术原因，每个星球只能发信号到比自己编号小的距离不超过 $l$ 的星球。特别地，强大的总基地可以接收任何波长的信号。每个星球处理接收到的数据需要 $1$ 个单位时间，传输时间可以忽略不计。

输入格式

第一行两个正整数 $n,l$。接下来 $n-1$ 行，总共第 $i$ 行包含了三个正整数 $x_i,y_i,l_i$，其中 $l_i$ 表示第 $i$ 个星球距离 $1$ 号星球 $l_i$ 的距离，$l_i$ 严格递增。

输出格式

总共 $n-1$ 行，每行一个数分别表示 $2$ 到 $n$ 号星球至少需要多少单位时间，总基地能够处理好数据，如果无法传到总基地则输出 $-1$。

3 1
1 2 1
2 3 2

1
2

3 3
1 2 1
2 3 2

1
1

数据规模与约定

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

对于 $100\%$ 的数据, $2 \le n \le 2.5 \times 10^5, 0 \le x_i,y_i,l_i \le 2\times 10^9, 1 \le l \le 2\times 10^9, x_i \le y_i$。

题目来源

By 俞华程