答えを二分探索します。判定問題が解ければよいです。 時給 \(k\) 以下でできる条件は、 \(\displaystyle\sum_{i\in I} (c_i - t_i k)\) が \(0\) 以下になるような道 \(i\in I\) たちを使って全体を連結にできることです。 これは最小全域木の要領で、 \(c_i - t_i k\) が小さい順に見て負なら必ず採用し、非負なら両端の頂点が連結でなければ採用すれば良いです。 これは Union Find などを用いれば実現可能です。計算量は二分探索の反復の回数を \(L\) とすると、ソートがボトルネックになり \(O(LM\log M)\) です。