The optimal approach is a greedy one as follows: at each point, train in the town with the smallest ~T_i~ value that can be reached, until town ~N~ can be reached. We can simulate this approach by maintaining the set of towns which are currently reachable (this set starts with only town ~1~, and then only expands), the smallest ~T_i~ value of any town in this set (this value can similarly only decrease), Pyglion's current level (initially ~1~), and the total time spent training so far (initially ~0~). Once the set of reachable towns includes town ~N~, we can stop and output the total time. If that never occurs and we're unable to expand the set any further, then town ~N~ must be unreachable from town ~1~, meaning that the answer is -1 instead.

One way to simulate this algorithm would be one level at a time – repeatedly iterating over all routes incident to all reachable towns, using ones with sufficiently low level requirements in order to expand the set of reachable towns, and then training to increase Pyglion's level by ~1~ if the set can't be expanded any more otherwise. If ~K~ is the maximum possible ~C_i~ value, then such an approach would take ~\mathcal O(M(N+K))~ time, which is too slow for full marks.

One thought is to modify this approach by repeatedly determining the minimum amount by which Pyglion's level must be increased in order to allow at least one new town to become reachable, and increasing it directly by that amount instead of by ~1~ level at a time. However, this implementation would still require ~\mathcal O(NM)~ time, which is also too slow.

For full marks, we must improve this implementation by avoiding repeatedly scanning over all routes incident to all reachable towns. This can be done in a manner very similar to Prim's algorithm for finding a graph's minimum spanning tree, by instead maintaining a priority queue of towns, ordered by the minimum level required for them to become reachable. At each step, we'll want to pop off the town which can be reached with the minimum possible level, and all of its adjacent towns can then be added to this priority queue. As we go, as before, we'll level up Pyglion as necessary to make each next town reachable, training at the already-reachable town with the smallest ~T_i~ value. The time complexity of this algorithm is ~\mathcal O(N+M \log N)~.