题目背景

原题为 P9126 [USACO23FEB] Moo Route II S

题目描述

某物流公司开发了新型传输系统，允许货物在时空通道中传输（可能产生时间回溯）。系统包含 $N$ 个物流中心（编号 $1$ 到 $N$）和 $M$ 条传输通道（$1 \leq N,M \leq 200000$）。第 $j$ 条通道特征为：

• 从物流中心 $u_j$ 在时间 $r_{j}$ 出发
• 在时间 $s_{j}$ 到达物流中心 $v_j$
• 允许 $s_{j} < r_{j}$（时间回溯）

货物在物流中心 $i$ 需处理 $a_i$ 时间（$1 \leq a_i \leq 10^9$）。若货物在时间 $s$ 到达中心 $i$，则只能使用出发时间 $r \geq s + a_i$ 的通道。

货物从中心 $1$ 出发，起始时间为 $0$。求每个中心 $i$ 最早可达时间（无法到达输出 $-1$）。

输入格式

第 $1$ 行：$N$ 和 $M$

第 $2 - (M+1)$ 行：每行 $u_j,r_{j}, v_j, s_{j}$

第 $(M+2)$ 行：$N$ 个整数$a_1,\cdots,a_N$

输出格式

$N$ 行，第 $i$ 行表示中心 $i$ 的最早到达时间

输入输出样例 #1

输入 #1

3 3
1 0 2 10
2 11 2 0
2 1 3 20
10 1 10

输出 #1

0
0
20

输入输出样例 #2

输入 #2

3 3
1 0 2 10
2 10 2 0
2 1 3 20
10 1 10

输出 #2

0
10
-1

样例解释

样例 1

货物路径：

1. 中心 1 (时间 0) → 通道 1 → 中心 2 (时间 10)
2. 中心 2 (时间 10) + 处理 1 → 通道 3 → 中心 3 (时间 20)

同时存在时间回溯路径：中心 2 (时间 10) → 通道 2 → 中心 2 (时间 0)

注意，在一开始的时候，是直接出发的，所以不用花时间处理货物。

样例 2

中心 2 处理需 1 单位时间，无法赶上出发时间为 10 的通道 2

数据范围

• 测试点 $1-5$：对于任意的 $j, r_{j} < s_{j}$（无时间回溯）
• 测试点 $6-10$：$N,M \leq 5000$
• 测试点 $11-20$：无特殊限制
• 对于所有测试点，满足 $1 \le N, M \le 2 \times 10^5$, $1 \le u_j, v_j \le N$, $0 \le r_j, s_j \le 10^9, 1 \le a_i \le 10^9$