1992: [USACO 2023 February Contest Silver] Problem 3. Moo Route II

Bessie is on vacation! Due to some recent technological advances, Bessie will travel via technologically sophisticated flights, which can even time travel. Furthermore, there are no issues if two "parallel" versions of Bessie ever meet.

In the country there are $N$ airports numbered $1,2,\dots ,N$ and $M$ time-traveling flights ($1\le N,M\le 200000$). Flight $j$ leaves airport $c_j$ at time $r_j$, and arrives in airport $d_j$ at time $s_j$ ($0\le r_j,s_j\le {10}^9$, $s_j<r_j$ is possible). In addition, she must leave $a_i$ time for a layover at airport $i$ ($1\le a_i\le {10}^9$). (That is to say, if Bessie takes a flight arriving in airport $i$ at time $s$, she can then transfer to a flight leaving the airport at time $r$ if $r\ge s+a_i$. The layovers do not affect when Bessie arrives at an airport.)

Bessie starts at city $1$ at time $0$. For each airport from $1$ to $N$, what is the earliest time when Bessie can get to at it?

The next $M$ lines describe flights. The $j$th of these lines contains $c_j$, $r_j$, $d_j$, $s_j$ in that order. ($1\le c_j,d_j\le N$, $0\le r_j,s_j\le {10}^9$)

The next line describes airports. It contains $N$ space separated integers, $a_1,\dots ,a_N$.

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

0
0
20