We only have to take into account such paths in which we reach to each city the earliest.

First, consider the following question.

Question: We want to travel from city \(A_i\) to city \(B_i\) on train \(i\). If you are in city \(A_i\) at time \(T\), what is the earliest time you can arrive at city \(B_i\)?

The answer for this question is \(\displaystyle{ \left\lceil \frac{T}{K_i} \right\rceil K_i + T_i}\). With this fact, one can solve the original problem with Dijkstra algorithm. The time complexity is \(O(N+M\log N)\).