Explorer space

 This is my solution to Codeforces round 718 div2 + div1 problem D: Explorer Space.

First we observe that it is only possible to return to $(i, j)$ iff $k$ is even. This is because for every step away from $(i, j)$ we need one step back, so we can pair up each step of a walk meaning $k$ must be even.

Next we observe that we can never have a different path in to $(i, j)$ than the path taken out from it. To prove this, suppose we could take a different path in, call it $p_{\text{in}}$, then we know the cost of $p_{\text{in}} \leq p_{\text{out}}$. But then we can swap $p_{\text{out}}$ with $p_{\text{in}}$, giving us a lower cost path.

Now we can use dynamic programming to compute the minimum cost path of length $k$. Concretely, let $dp_{i, j, k}$ denote the minimum cost path to $(i, j)$ with exactly $k$ steps. Then

$$dp_{i, j, k} = \min_{\text{all edges $e$ incident to $(i, j)$}}{dp_{e, k-1} + w_e}$$

This solution takes $O(nmk)$ time.