minimum spanning tree mst is going to use an undirected graph pylint disabletoofewpublicmethods an edge of an undirected graph the disjoint set is represented with an list n of integers where ni is the parent of the node at position i if ni i i it s a root or a head of a set args n int number of vertices in the graph args node1 node2 int indexes of nodes whose sets will be merged get the set of nodes at position a and b if a and b are the roots this will be constant o1 join the shortest node to the longest minimizing tree size faster find get the root element of the set containing a very important memoize result of the recursion in the list to optimize next calls and make this operation practically constant o1 node a it s the set root so we can return that index args vertexcount int number of vertices in the graph edges list of edge edges of the graph forest disjointset disjointset of the vertices returns int sum of weights of the minnimum spanning tree kruskal algorithm this algorithm will find the optimal graph with less edges and less total weight to connect all vertices mst the mst will always contain n1 edges because it s the minimum required to connect n vertices procedure sort the edges criteria less weight only take edges of nodes in different sets if we take a edge we need to merge the sets to discard these after repeat this until select n1 edges we will have the complete mst if we have selected n1 edges all the other edges will be discarted so we can stop here test how input works input consists of different weighted connected undirected graphs line 1 integers n m lines 2 m2 edge with the format node index u node index v integer weight samples of input 5 6 1 2 3 1 3 8 2 4 5 3 4 2 3 5 4 4 5 6 3 3 2 1 20 3 1 20 2 3 100 sum of weights of the optimal paths 14 40 read m edges from input after finish input and graph creation use kruskal algorithm for mst pylint disable too few public methods an edge of an undirected graph the disjoint set is represented with an list n of integers where n i is the parent of the node at position i if n i i i it s a root or a head of a set args n int number of vertices in the graph contains wich node is the parent of the node at poisition i contains size of node at index i used to optimize merge make all nodes his own parent creating n sets args node1 node2 int indexes of nodes whose sets will be merged get the set of nodes at position a and b if a and b are the roots this will be constant o 1 join the shortest node to the longest minimizing tree size faster find merge set a and set b add size of old set a to set b merge set b and set a add size of old set b to set a get the root element of the set containing a very important memoize result of the recursion in the list to optimize next calls and make this operation practically constant o 1 node a it s the set root so we can return that index args vertex_count int number of vertices in the graph edges list of edge edges of the graph forest disjointset disjointset of the vertices returns int sum of weights of the minnimum spanning tree kruskal algorithm this algorithm will find the optimal graph with less edges and less total weight to connect all vertices mst the mst will always contain n 1 edges because it s the minimum required to connect n vertices procedure sort the edges criteria less weight only take edges of nodes in different sets if we take a edge we need to merge the sets to discard these after repeat this until select n 1 edges we will have the complete mst list of edges taken minimum spanning tree set of the node u set of the node v if we have selected n 1 edges all the other edges will be discarted so we can stop here test how input works input consists of different weighted connected undirected graphs line 1 integers n m lines 2 m 2 edge with the format node index u node index v integer weight samples of input 5 6 1 2 3 1 3 8 2 4 5 3 4 2 3 5 4 4 5 6 3 3 2 1 20 3 1 20 2 3 100 sum of weights of the optimal paths 14 40 create list of size m read m edges from input convert from 1 indexed to 0 indexed convert from 1 indexed to 0 indexed after finish input and graph creation use kruskal algorithm for mst
import sys


class Edge:
    

    def __init__(self, source, target, weight):
        self.source = source
        self.target = target
        self.weight = weight


class DisjointSet:
    

    def __init__(self, size):
        

        self.parent = [None] * size 
        self.size = [1] * size 
        for i in range(size):
            self.parent[i] = i 

    def merge_set(self, node1, node2):
        

        
        
        node1 = self.find_set(node1)
        node2 = self.find_set(node2)

        
        if self.size[node1] < self.size[node2]:
            self.parent[node1] = node2 
            self.size[node2] += self.size[node1] 
        else:
            self.parent[node2] = node1 
            self.size[node1] += self.size[node2] 

    def find_set(self, node):
        
        if self.parent[node] != node:
            
            
            
            self.parent[node] = self.find_set(self.parent[node])

        
        return self.parent[node]


def kruskal(vertex_count, edges, forest):
    
    edges.sort(key=lambda edge: edge.weight)

    mst = [] 

    for edge in edges:
        set_u = forest.find_set(edge.u) 
        set_v = forest.find_set(edge.v) 
        if set_u != set_v:
            forest.merge_set(set_u, set_v)
            mst.append(edge)
            if len(mst) == vertex_count-1:
                
                
                break

    return sum([edge.weight for edge in mst])


def main():
    
    for size in sys.stdin:
        vertex_count, edge_count = map(int, size.split())
        forest = DisjointSet(edge_count)
        edges = [None] * edge_count 

        
        for i in range(edge_count):
            source, target, weight = map(int, input().split())
            source -= 1 
            target -= 1 
            edges[i] = Edge(source, target, weight)

        
        print("MST weights sum:", kruskal(vertex_count, edges, forest))

if __name__ == "__main__":
    main()