Because T is a regular language and M is represented by a finite automaton, it follows that T and L can themselves be represented as finite automata.
steps 2 and 3 can be solved using weighted finite-state intersection and single-source shortest path algorithms, respectively (Mohri 2009).