all pairs shortest path using Dijkstra
Hint: If you have all-pairs shortest-paths information, and if you are considering placing a store at city X, can you compute the max distance from any city to a store?  You could now enumerate all possibilities for city X.  What's the running time of this algorithm?



An alternative approach: 

Hint: If you add a new source vertex and add edges from it to _______, and then use Dijkstra's algorithm to compute single-source shortest-paths starting from that source, does that give you any useful information that will help you?  (You'll have to fill in the blank somehow.)