#Q4 Loud music for everyone
# using Kruskal's Algorithm
def lowest_cost(conduits_info_str):
    """take the information about conduits between classroom and returns the lowest cost the university can pay to get this job done."""
    lines = conduits_info_str.splitlines()
    num_vertices = int(lines[0].split()[1])
    weighty = []
    graph = [{i} for i in range(num_vertices)]
    T = []
    for i in lines[1:]:
        nums = [int(j) for j in i.split()]
        s = nums[0]
        e = nums[1]
        w = nums[2]
        x = (w, s, e)
        weighty.append(x)
    count = 0
    weighty.sort()
    while count < num_vertices-1:
        for (w,i,j) in weighty:
            if comp(graph, i).isdisjoint(comp(graph, j)):
                graph[i] = graph[i].union(graph[j])
                graph[j] = graph[i].union(graph[j])
                T.append(w)
                count+=1
            elif w == weighty[-1][0]:
                count = num_vertices
    return sum(T)*50

def comp(lst, n):
    new = {n}
    for i in lst[n]:
        new.update(lst[i])
    return new