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.