Let $G$ is a Cartesian product of two arbitrary directed weighted graphs $M$ and $N$. Weights are from non-commutative finite idempotent semiring.

Are there exist advanced results on single source shortest path (SSSP) problem for $G$? Suppose that $|V_M| = |V_N| = n$. Is it possible to solve SSSP in $\widetilde{O}(BMM(n))$?