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://mirror.codeforces.com/contest/1422/submission/95066276

Edit: Nvm, I'm very stupid. When I ran Dijkstra, the set was like this: {node, distance} when it should have been {distance, node}, so everything was sorted after the value of the nodes instead of the distance, so that's the reason for TLE. Also on line 14 I made a small typo: "ans=abs(sx-fx)+abs(sy+fy);" instead of "ans=abs(sx-fx)+abs(sy-fy);", so after fixing TLE that gave me WA on test 5.