Suppose we are given a directed graph $G = (V, E)$ with edge weights $w : E \rightarrow \mathbb{R}$ (we can assume there are no negative cycles) and edge labels $\ell : E \rightarrow \Sigma$ from some alphabet $\Sigma$. We are also given a description of an NFA $M$ (or DFA, or regular expression)...