Basically for every node I calculate the 4 closest nodes in all four directions, so the number of edges should be at most 4*M, right?

After that I run Dijkstra but for some reason I get TLE on test 5, I spent a lot of hours trying to see why but with no success, that's why I'm asking for some help, I just don't know what's wrong with my implementation.

Code link: https://codeforces.net/contest/1422/submission/95066276