P7984 [USACO21DEC] Tickets P

Bessie 正在参加远足旅行！她当前正在旅行的路线由编号为 $1\ldots N$（$1\le N\le 10^5$）的 $N$ 个检查点组成。 有 $K$（$1\le K\le 10^5$）张票可供购买。第 $i$ 张票可以在检查站 $c_i$（$1\le c_i\le N$）以 $p_i$（$1\le p_i\le 10^9$）的价格购得，并且可以用其进入所有检查站 $[a_i,b_i]$（$1\le a_i\le b_i\le N$）。在进入任何检查站之前，Bessie 必须已购买一张允许其进入该检查站的票。一旦 Bessie 可以前往某一检查站，她就可以在未来的任何时候回到该检查站。 对于每一个 $i\in [1,N]$，如果 Bessie 最初只能进入检查点 $i$，输出使得可以进入检查点 $1$ 和 $N$ 所需的最低总价。如果无法这样做，输出 $-1$。

无

无

【样例解释】 如果 Bessie 从检查点 $i=4$ 开始，那么一种购得进入检查点 $1$ 和 $N$ 的方法如下： 在检查点 $4$ 购买第一张票，使 Bessie 可以进入检查点 $2$ 和 $3$。 在检查点 $2$ 购买第三张票，使 Bessie 可以进入检查点 $7$。 回到检查点 $4$ 购买第二张票，使 Bessie 可以进入检查点 $5$ 和 $6$。 在检查点 $6$ 购买第四张票，使 Bessie 可以进入检查点 $1$。 【数据范围】 - 测试点 1-7 满足 $N,K\le 1000$。 - 测试点 8-19 没有额外限制。