def find(parent, vertex):
    while parent[vertex] != vertex:
        parent[vertex] = parent[parent[vertex]]  # path compression
        vertex = parent[vertex]
    return vertex

def union(parent, rank, v1, v2):
    root1, root2 = find(parent, v1), find(parent, v2)
    if root1 == root2:
        return False  # already connected: adding this edge would form a cycle
    if rank[root1] < rank[root2]:
        root1, root2 = root2, root1
    parent[root2] = root1
    if rank[root1] == rank[root2]:
        rank[root1] += 1
    return True

def kruskal(vertices, edges):
    parent = {v: v for v in vertices}
    rank = {v: 0 for v in vertices}
    mst = []

    for weight, v1, v2 in sorted(edges):
        if union(parent, rank, v1, v2):
            mst.append((v1, v2, weight))

    return mst

vertices = ["A", "B", "C", "D"]
edges = [(1, "A", "B"), (4, "A", "C"), (3, "B", "C"), (2, "B", "D"), (5, "C", "D")]

print(kruskal(vertices, edges))
# [('A', 'B', 1), ('B', 'D', 2), ('B', 'C', 3)]