What if we model the cities as a graph?
Build a graph of cities and find the minimum spanning tree.
You can use a variation of the Kruskal's algorithm for that.
Sort the edges by their cost and use a union-find data structure.
How to check all cities are connected?
At the beginning we have n connected components, each time we connect two components the number of connected components is reduced by one. At the end we should end with only a single component otherwise return -1.