Moo Route II

Bessie는 휴가 중입니다. 최근 기술 발전 덕분에 Bessie는 시간 여행까지 가능한 첨단 항공편을 이용해 이동합니다. 평행 세계의 Bessie 두 명이 만나도 문제가 되지 않습니다.

이 나라에는 번호가 $1, 2, \ldots, N$인 공항이 $N$개 있고, 시간 여행 항공편은 $M$개 있습니다($1\leq N, M \leq 200000$). $j$번째 항공편은 공항 $c_j$에서 시각 $r_j$에 출발하여 공항 $d_j$에 시각 $s_j$에 도착합니다($0 \leq r_j, s_j \leq 10^9$). $s_j < r_j$인 경우도 있을 수 있습니다. 공항 $i$에서는 환승에 $a_i$만큼의 시간이 필요합니다($1\leq a_i\leq 10^9$). 즉, 어떤 항공편을 타고 시각 $s$에 공항 $i$에 도착했다면, $r \geq s + a_i$를 만족하는 시각 $r$에 공항 $i$에서 출발하는 항공편으로 갈아탈 수 있습니다. 환승 시간은 Bessie가 공항에 도착하는 시각에 영향을 주지 않습니다.

Bessie는 시각 0에 도시 1에서 출발합니다. 1번부터 $N$번까지 각 공항에 대해, Bessie가 도착할 수 있는 가장 이른 시각을 구하십시오.

첫째 줄에 $N$과 $M$이 주어집니다. 다음 $M$개의 줄에는 순서대로 $c_j$, $r_j$, $d_j$, $s_j$가 주어집니다($1\leq c_j, d_j \leq N$, $0\leq r_j, s_j \leq 10^9$). 마지막 줄에는 공백으로 구분된 $N$개의 정수 $a_1, \ldots, a_N$이 주어집니다.

$N$개의 줄을 출력합니다. $i$번째 줄에는 Bessie가 공항 $i$에 도착할 수 있는 가장 이른 시각을 출력합니다. 도착할 수 없으면 -1을 출력합니다.