Hacker earth circuits problem train and cities

I tried this question with Dijkstra algorithm but I am getting TLE and hacker earth didn’t provide any editorial yet so any one can help me with this problem Train lines and cities | Practice Problems