This problem can be solved in polynomial time by a product construction. Construct the graph $G^\prime$ as follows:
* The vertices of $G^\prime$ are $(V \times M) \cup {#}$, i.e. all pairs of a vertex of $G$ and a state of $M$, together with an extra vertex identified by the arbitrary symbol $#$.
* For each edge in $e \in E$ from $v_1$ to $v_2$, add an edge in $G^\prime$ from $(v_1, m_1)$ to $(v_2, m_2)$ with weight $w(e)$ if and only if there is an edge in $M$ from $m_1$ to $m_2$ that is labeled $\ell(e)$.
* For each accepting state $m$ in $M$, add an edge in $G^\prime$ from $(t, m)$ to $#$ with weight 0.
Then the shortest path in $G^\prime$ from $(s, m_0)$ to $#$ (where $m_0$ is the initial state of $M$) gives the shortest path in $G$ from $s$ to $t$ matching $L(M)$. 433
There cannot be a negative cycle in $G^\prime$, since dropping the $m$ states from the vertex labels would give a negative cycle in $G$, which we are assuming does not exist.
This also answers the question if $M$ is a DFA or regular expression instead of an NFA, since these can be converted to an equivalent NFA in polynomial time. We can also directly handle NFAs with $\varepsilon$-transitions: if $M$ contains an $\varepsilon$-transition from $m_1$ to $m_2$, add an edge in $G^\prime$ with weight 0 from $(v, m_1)$ to $(v, m_2)$ for each $v \in V$.
For fixed $M$, the product graph $G^\prime$ has only linearly more vertices and edges than the original graph $G$. This means that any fixed problem of the form "find the shortest path that visits edges in such-and-such order", such as the problems linked in the question, can be solved just as fast as the ordinary shortest path problem asymptotically.
As an implementation detail, note that there is no need to actually write down the whole product graph in memory. The vertices and edges can be generated dynamically while running the shortest path algorithm, which allows unused vertices to be skipped entirely. 433