U414043 [USACO23FEB] Moo Route II S 数据加强版

Bessie 正在旅游！有 $n$ 个城市和 $m$ 条航线，第 $i$ 条航线有 $(c_i,r_i,d_i,s_i)(1\leq c_i, d_i\leq n,0\leq r_i,s_i\leq 10^9)$ 的限制，表示从 $c_i$ 到 $d_i$，最迟 $r_i$ 时进入，$s_i$ 时到达，注意 $r_i$ 可能大于 $s_i$。第 $i$ 个城市有 $a_i(a_i \le 10^9)$ 的停泊时间，表示 **乘坐航班到达** $i$ 后，需要等待 $a_i$ 的时间后才能继续飞行。问到达每个城市的最早时间？如果不能到达，输出 `-1`。 Bessie $0$ 时刻在 $1$ 城市。

第一行两个整数 $n,m$。 接下来 $m$ 行每行四个整数 $c_i,r_i,d_i,s_i$。 接下来一行 $n$ 个整数，表示 $a_i$。

$n$ 行，第 $i$ 行一个整数表示到达 $i$ 的最早时间，不能到达输出 `-1`。

$1 \le n,m \le 200000$