Consider the following application problem. You are the transport minister of your country.The recent disaster devastated the road network connecting all of the key locations. Thus you are to plan out the optimal roads to connect the key locations together, based on the following criteria: You want to connect all key locationstogether; but theydo not need to be directly connected. You are given the importance of directly connecting 2 key locations together; for all key location pairs. The importance is represented by a number for each pair of locations, and the highest this number is, the most important it is to directly connect the 2 key locations. You are given the cost of directly connecting 2 key locations together, for all key location pairs. For cost savings reasons, you should not build redundant roads:between any pair of locations, there should be only one possible path. You want to maximise the importance of connecting all key locations together. If there are multiple ways of achieving the maximum value of the importance, then you should pick the one that minimises the cost of the selected roads. Describe how you would model this problem as a graph and algorithmically solve this problem efficiently using an algorithm you have learnt in the unit