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()

Z3JhcGggPSB7CiAgICAiQSIgOiB7IkIiIDogMTMsICJDIiA6IDMsICJEIiA6IDksICJFIiA6IDl9LAogICAgIkIiIDogeyJBIiA6IDEzLCAiQyIgOiAxMSwgIkQiIDogMTEsICJFIiA6IDEzfSwKICAgICJDIiA6IHsiQSIgOiAzLCAiQiIgOiAxMSwgIkQiIDogOSwgIkUiIDogN30sCiAgICAiRCIgOiB7IkEiIDogOSwgIkIiIDogMTEsICJDIiA6IDksICJFIiA6IDJ9LAogICAgIkUiIDogeyJBIiA6IDksICJCIiA6IDEzLCAiQyIgOiA3LCAiRCIgOiAyfSwKfQoKTm90QWxsb3dlZE5vZGVzID0gewogICAgIkEiIDogW10sCiAgICAiQiIgOiBbXSwKICAgICJDIiA6IFtdLAogICAgIkQiIDogW10sCiAgICAiRSIgOiBbXSwKfQoKZGVmIGJ1aWxkX29zdF90cmVlKCk6CiAgICBmb3IgdHVwIGluIGdldF9zb3J0ZWRfbm9kZXMoKToKICAgICAgICBub2RlLCBlZGdlLCB2YWx1ZSA9IHR1cAogICAgICAgIHByaW50KCJOT0RFIHwgRURHRSB8IE5vdEFsbG93ZWROb2RlcyA9PiAiLCBub2RlLCBlZGdlLCAiTk9ERVMgW25vZGUgfCBlZGdlXSA9PiAiLCAgTm90QWxsb3dlZE5vZGVzW25vZGVdLCBOb3RBbGxvd2VkTm9kZXNbZWRnZV0pCiAgICAgICAgaWYgbm90IGN5Y2xlX3Rlc3QoZWRnZSwgbm9kZSk6CiAgICAgICAgICAgIGNvbnRpbnVlCgogICAgICAgIGNvbm5lY3Rfbm9kZShlZGdlLCBub2RlKQogICAgICAgIHByaW50KG5vZGUsIGVkZ2UpCgoKCmRlZiBnZXRfc29ydGVkX25vZGVzKCk6CiAgICByZXR1cm4gc29ydGVkKFsoa2V5LCB0dXBbMF0sIHR1cFsxXSkgZm9yIGtleSBpbiBncmFwaCBmb3IgdHVwIGluIGdyYXBoW2tleV0uaXRlbXMoKV0sIGtleT1sYW1iZGEgeDogeFsyXSkKCgoKZGVmIGNvbm5lY3Rfbm9kZShrZXksIG5vZGUpOgogICAgTm90QWxsb3dlZE5vZGVzW2tleV0uYXBwZW5kKG5vZGUpCiAgICBOb3RBbGxvd2VkTm9kZXNbbm9kZV0uYXBwZW5kKGtleSkKCgoKZGVmIGN5Y2xlX3Rlc3Qoc3RhcnQsIGVuZCwgdmlzaXRlZD1bXSk6CgoKICAgIGlmIHN0YXJ0IGluIHZpc2l0ZWQ6CiAgICAgICAgcmV0dXJuIEZhbHNlCiAgICB2aXNpdGVkLmFwcGVuZChzdGFydCkKICAgIGlmIGVuZCBpbiBOb3RBbGxvd2VkTm9kZXNbc3RhcnRdOgogICAgICAgIHJldHVybiBGYWxzZQogICAgZWxpZiBzdGFydCBpbiBOb3RBbGxvd2VkTm9kZXNbZW5kXToKICAgICAgICByZXR1cm4gRmFsc2UKICAgIGVsc2U6CiAgICAgICAgZm9yIGVsZW1lbnQgaW4gTm90QWxsb3dlZE5vZGVzW3N0YXJ0XToKICAgICAgICAgICAgaWYgZWxlbWVudCBub3QgaW4gdmlzaXRlZDoKICAgICAgICAgICAgICAgIGN5Y2xlX3Rlc3QoZWxlbWVudCwgZW5kLCB2aXNpdGVkKQogICAgcmV0dXJuIFRydWUKCgpidWlsZF9vc3RfdHJlZSgp