时间限制：1秒　　内存限制：256M

---

【问题描述】

　　C国的航空技术如此的发达，甚至可以进行时间旅行。

　　在这个国家，有 \(N\) 个机场，编号为 \(1,2,\cdots,N\)，还有 \(M\) 条时间旅行航班（\(1 \leq N,M \leq 200000\)）。第 \(i\) 条航班从机场 \(a_i\) 在时间 \(s_i\) 起飞，并在时间 \(t_i\) 抵达机场 \(b_i\)（\(0 \leq s_i,t_i \leq 10^9\)，且\(s_i < t_i\) 是可能的）。此外，在进行时间旅行时，每到达一个机场，都必须停留不少于 \(d_i\) 的时间（\(1 \leq d_i \leq 10^9\)）。也就是说，某人乘坐一趟航班在时间 \(t\) 抵达机场 \(i\)，她可以转乘一趟从该机场出发的航班，只要该航班的起飞时间 \(s \geq t + d_i\)。

　　小H 从机场 \(1\) 出发，起始时间为 \(0\)。请你求出他到 \(1\) 到 \(N\) 的每个机场的最早时间。

【输入格式】

　　第一行输入包含两个整数 \(N\) 和 \(M\)。
　　接下来的 \(M\) 行描述航班信息。其中第 \(i\) 行包含 \(a_i, s_i, b_i, t_i\)，依次表示航班的起飞机场、起飞时间、降落机场和降落时间。\((1 \leq a_i,b_i \leq N, 0 \leq s_i,t_i \leq 10^9)\)
　　接下来的一行描述每个机场的停留时间。该行包含 \(N\) 个用空格分隔的整数，分别为 \(d_1,\cdots,d_N\)。

【输出格式】

　　输出共 \(N\) 行。第 \(i\) 行输出 小H 最早到达机场 \(i\) 的时间；如果无法到达该机场，输出 \(-1\)。

【输入输出样例1】

　Input

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

　Output

0
0
20

【样例1解释】

　　小H 可以按照给定的顺序乘坐第 \(3\) 班航班，这使她可以在时间 \(0\) 到达机场 \(1\) 和机场 \(2\)，以及在时间 \(20\) 到达机场 \(3\)。
　　注意，这条路线会两次经过机场 \(2\)，第一次是在时间 \(10-11\)，第二次是在时间 \(0-1\)。

【输入输出样例2】

　Input

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

　Output

0
10
-1

【样例2解释】

　　在这个例子中，小H 可以乘坐第 \(1\) 班航班，在时间 \(10\) 抵达机场 \(2\)。但是，她无法及时赶上第 \(2\) 班航班，因为该航班的起飞时间为 \(10\)，而她需要至少 \(1\) 个时间单位来完成停留。

【数据限制】

　　 - 测试点 \(3-5\)：对于每个 \(i\)，\(s_i < t_i\)，也就是说所有航班的到达时间晚于起飞时间。
　　- 测试点 \(6-10\)：\(N,M \leq 5000\)
　　- 测试点 \(11-20\)：无额外限制。

【来源】

　　Mr.he