Given $n$ cities, I'm looking to build a transportation system that allows travelling between every two cities. For every two cities $i$ and $j$, a road can be paved in the cost of $c_{ij}$. Also, it is possible to establish an airport in city $i$ in the cost of $a_i$ (all costs are positive). One can travel between two cities if there is a road between them or if there are airports in both cities. I'm seeking for efficient algorithm to find transportation system in the minimal cost, such that it will be possible to travel between every two cities (Not necessarily directly).
My thoughts:
Generally, I thought to set $n$ nodes, one for each city, and connect each of them with weighted edges, such that the weight of each edge will be the cost of travel between two cities.
Then, I could run Kruskal's algorithm to find MST, which will be the transportation system I'm looking for.
I'm trying to figure out how to set the weight of every edge, which will indicate the cost of travelling between two cities.
First, I thought to calculate the $\min(c_{ij}, a_i + a_j)$, but then if I choose to establish an airport in some cities $i$ and $j$, it's going to effect the way I can travel between $i$ and some other city $k$.
So I got stuck in how to choose the weights of the edges, and I'm not sure how to continue from here.
EDIT: I thought of a different approach:
Build graph in which every node represents a node, and every edge's weight between two nodes (cities) $i$ and $j$ will be $c_{ij}$
In addition, I'll add another node which will be connected to all the other nodes, with weight $a_i$ to node $i$.
So the additional node will represent the airport.
Now, we can run algorithm to find MST, but this doesn't seem to work for some examples I've tried.
Any help appreciated.
