Use Floyd-Warshall's algorithm to compute any-point to any-point distances. (Or can also do Dijkstra from every node due to the weights are non-negative).

For each city calculate the number of reachable cities within the threshold, then search for the optimal city.