New roads

Bitland has n cities that initially have no connecting roads. The goal is to connect all cities to each other.

You are given a set of possible roads and the construction cost for each road. What is the smallest cost of a road network that connects all cities?

You may assume that the number of cities is at most 50 and that the methods of the class are called at most 100 times. The cost of each road is an integer in the range 1 \dots 1000.

In a file newroads.py, implement a class NewRoads with the following methods:

• constructor with the number of cities as a parameter
• add_road adds a possible road of cost x between cities a and b
• min_cost returns the smallest cost of connecting all cities (or −1 if it is not possible to connect all cities)

class NewRoads:
    def __init__(self,n):
        # TODO

    def add_road(self,a,b,x):
        # TODO

    def min_cost(self):
        # TODO

if __name__ == "__main__":
    n = NewRoads(4)
    n.add_road(1,2,2)
    n.add_road(1,3,5)
    print(n.min_cost()) # -1
    n.add_road(3,4,4)
    print(n.min_cost()) # 11
    n.add_road(2,3,1)
    print(n.min_cost()) # 7