各都市へ最も早く到達する移動経路のみを考えれば十分です。

まず、次のような問題を考えます。

問題：鉄道 \(i\) を使って都市 \(A_i\) から都市 \(B_i\) に移動する。時刻 \(T\) に都市 \(A_i\) にいるとき、都市 \(B_i\) には最短でいつ着けるか？

この問題に対する答えは \(\displaystyle{ \left\lceil \frac{T}{K_i} \right\rceil K_i + T_i}\) です。このことを使い、ダイクストラ法を用いて元の問題を解くことができます。計算量は \(O(N+M\log N)\) です。