# 返回最小的花费代价使得这n户人家连接起来
# @param n int整型 n户人家的村庄
# @param m int整型 m条路
# @param cost int整型二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
# @return int整型

# 最小生成树： 最小生成树包含原图的所有节点而只用最少的边和最小的权值距离
# 视频学习：https://www.bilibili.com/video/BV1d34y1R7xA/?spm_id_from=333.337.search-card.all.click&vd_source=e0d139ef9278fd07bd20752f3c433bb0
# 算法思想 :将所有边的权值按照从小到大做升序排序，从最小的开始选择，新加入的只要不与原来的边构成环路，就可加入到最小生成树的
    # • 树中没有环
    # • 所有的顶点都要在树中
    # • 对于N条顶点，有N-1条边

class Solution:
    def miniSpanningTree(self , n , m, cost):
        'n个顶点， m条边'
        '首先对图中的边按照边权从小到大排序'
        cost=sorted(cost, key=lambda x: x[2])
        # tag 即为顶点的标记字典，可以通过顶点查询它的标记
        tag={i : i for i in range(1,n+1)} # 每个点的父节点初始化为自己，key是自己，value是标号。
        result=[] # len(result)=边数=顶点-1
        sum=0
        '遍历每一条边'
        for u,v,w in cost:
            # u,v是顶点，w是边的权重
            '如果两个顶点对应的值不相等（不产生回路）将边加入到最小生成树中' \
            '如果相同（有回路，跳过此边）'
            if (tag[u]!=tag[v]):
                result.append([u,v,w])
                # 把边对应的两个节点对应的编号置为相同，大的向小的看齐。
                max_v = max(tag[u], tag[v]) # 找顶点标号大的
                min_v = min(tag[u], tag[v]) # 找顶点标号小的
                for i in range(1, n+1):  # 找所有的顶点
                    if tag[i] == max_v: # 顶点对应的标号等于大的那个
                        tag[i] = min_v  # 大的标号向小的标号看齐
                sum+=w
                if(len(result)==n-1):
                    return sum
        return sum