There are n cities and m possible bidirectional roads and k temple. build roads with minimum cost such that each city has access to at least 1 temple

There are n cities and m possible roads and k temples. The cost of each road is given. Build roads with minimum cost such that each city has access to at least 1 temple.

Note that there can be multiple roads(edges) between two cities and each temple is inside a city.

My attempt : I tried running Kruskal's Algorithm of the graph and then sort edges in descending order and then remove them one by one if the graph still satisfies the condition. I don't know this algorithm is correct or not.

I found this question in an algorithm book.

• Please credit the original source of this problem. Nov 26 '21 at 16:06

Add a new vertex $$v$$ to the graph. For every city node $$u$$ that contains a temple, add a $$0$$ weighted edge $$(v,u)$$ to the graph. Let the new graph be $$G'$$. Find the minimum spanning tree of $$G'$$. It would give the minimum cost of constructing roads such that every city has access to at least one temple.