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 https://www.hackerearth.com/practice/algorithms/graphs/shortest-path-algorithms/practice-problems/approximate/trains-and-costs-8b8bbea4/description/