It was a minimum spanning tree problem. For Wakanda to be connected it needs (number of cities that have people on it) - 1 edges . Start adding edges in the MST where both city u and v have people on it . If the number of edges ( cnt ) that are added in the MST are less than (cities-1) then we have to add (cities-1-cnt) more edges in the MST for Wakanda to be connected and each of those edges will have length d.