AT_abc414_g [ABC414G] AtCoder Express 4

AtCoder 王国有一条东西向的铁路线，这条线路上有 $1,2,\ldots,N$ 号车站。第 $i$ 号车站（$1\leq i\leq N$）位于坐标 $x_i$ 上（$x_1 < x_2 < \ldots < x_N$）。 在这条线路上，AtCoder Express 公司运营着 $M$ 种特急列车。 第 $i$ 种特急列车的运行方式如下： - 可以在第 $l_i,l_i+1,\ldots,r_i$ 号车站中的任意一个上车。 - 可以在第 $L_i,L_i+1,\ldots,R_i$ 号车站中的任意一个下车。此时，列车的行驶方向仅为东西某一方向，满足 $r_i < L_i$ 或 $R_i < l_i$。 - 票价为初乘票价 $c_i$，再加上上车站到下车站的距离。具体来说，从第 $s$ 号车站（$l_i\leq s\leq r_i$）乘车到第 $t$ 号车站（$L_i\leq t\leq R_i$）时，票价为 $c_i+|x_s-x_t|$。 你现在在第 $1$ 号车站。对于每个 $k$（$2\leq k\leq N$），请判断是否可以通过换乘特急列车从第 $1$ 号车站到达第 $k$ 号车站。如果可以到达，请求出所需总票价的最小值。

输入按以下格式从标准输入给出。 > $N$ $M$ > $x_1$ $x_2$ $\ldots$ $x_N$ > $l_1$ $r_1$ $L_1$ $R_1$ $c_1$ > $l_2$ $r_2$ $L_2$ $R_2$ $c_2$ > $\vdots$ > $l_M$ $r_M$ $L_M$ $R_M$ $c_M$

请按以下格式输出答案。 > $\mathrm{ans}_2$ $\mathrm{ans}_3$ $\ldots$ $\mathrm{ans}_N$ $\mathrm{ans}_i$ 表示 $k=i$ 时的答案。如果可以从第 $1$ 号车站到达第 $i$ 号车站，则输出所需总票价的最小值；否则输出 $-1$。

### 限制条件 - $2\leq N\leq 10^5$ - $1\leq M\leq 10^5$ - $0\leq x_1 < x_2 < \ldots < x_N \leq 10^{12}$ - $1\leq l_i\leq r_i\leq N,\ 1\leq L_i\leq R_i\leq N$ - 满足 $r_i < L_i$ 或 $R_i < l_i$ - $1\leq c_i\leq 10^{12}$ - 输入均为整数 ### 样例说明 1 可以如下到达第 $2$ 号车站： 1. 乘坐第 $1$ 种特急列车，从第 $1$ 号车站上车，在第 $6$ 号车站下车。票价为 $c_1+|x_1-x_6|=100+|0-150|=250$。 2. 乘坐第 $3$ 种特急列车，从第 $6$ 号车站上车，在第 $2$ 号车站下车。票价为 $c_3+|x_6-x_2|=30+|150-20|=160$。 此时总票价为 $410$，且这是最小值。无法到达第 $4$ 号车站。 由 ChatGPT 4.1 翻译