First, we generate an array of \(2M\) events, with each event representing a scheduled departure or arrival of a train. Sort these events by time, breaking ties in favor of arrivals (i.e. arrivals will be processed before departures if they happen on the same time).

Let’s have an array \(D_i: 1 \leq i \leq N\), all initialized to \(0\), to represent the latest true arrival time at city \(i\) of all events processed so far.

Also initialize \(X_i: 1 \leq i \leq M\). \(X_1\) should be as given in the input, and the rest should be \(0\).

Now process the events:

• for a “departure” event, we’ve already processed all the arrivals of trains that could transfer to this train, so the train must be delayed by at least \(D_{A_i} - S_i\); therefore set \(X_i \larr \max (X_i, D_{A_i} - S_i)\)
• for an “arrival” event, we’ve already processed the departure event for this train and know its delay, so we should update \(D_{B_i}\) with the true arrival time of this train: \(D_{B_i} \larr \max (D_{B_i}, T_i + X_i)\)

This solution should take \(O(N + M \log M)\) time, with the bottleneck being sorting the events.