My old C++ solution got AC with optimized Dijkstra, O(v*log(v)), where v = m*n.
The timing was 0,406 sec.

Evidently, with Python (2.7, 3.4) I got TLE with the same solution. On my machine 500*500 case runs for 4.5 seconds.

Then I realized O(m*n) solution and optimized input as much as possible (Python). It still gives TLE16, on my machine - runs for 2.3 seconds.

Then I run code under PyPy (5.4.1, Python2.7 compatible) and on my machine it runs for 0.383 seconds only. I hope it would AC if PyPy is able to be selected as a programming language.

Please add PyPy!
Thanks