Notice that the path you take to buy an apple will be the same path to return to the starting city.

Starting from each city, use Dijkstra’s algorithm to find the best city to travel to.