graph = {
    "A" : {"B" : 13, "C" : 3, "D" : 9, "E" : 9},
    "B" : {"A" : 13, "C" : 11, "D" : 11, "E" : 13},
    "C" : {"A" : 3, "B" : 11, "D" : 9, "E" : 7},
    "D" : {"A" : 9, "B" : 11, "C" : 9, "E" : 2},
    "E" : {"A" : 9, "B" : 13, "C" : 7, "D" : 2},
}

NotAllowedNodes = {
    "A" : [],
    "B" : [],
    "C" : [],
    "D" : [],
    "E" : [],
}

def build_ost_tree():
    for tup in get_sorted_nodes():
        node, edge, value = tup
        print("NODE | EDGE | NotAllowedNodes => ", node, edge, "NODES [node | edge] => ",  NotAllowedNodes[node], NotAllowedNodes[edge])
        if not cycle_test(edge, node):
            continue

        connect_node(edge, node)
        print(node, edge)



def get_sorted_nodes():
    return sorted([(key, tup[0], tup[1]) for key in graph for tup in graph[key].items()], key=lambda x: x[2])



def connect_node(key, node):
    NotAllowedNodes[key].append(node)
    NotAllowedNodes[node].append(key)



def cycle_test(start, end, visited=[]):


    if start in visited:
        return False
    visited.append(start)
    if end in NotAllowedNodes[start]:
        return False
    elif start in NotAllowedNodes[end]:
        return False
    else:
        for element in NotAllowedNodes[start]:
            if element not in visited:
                cycle_test(element, end, visited)
    return True


build_ost_tree()