#include <iostream>
using namespace std;

int numVertices,numEdges;
int *parent,*weight,numTrees;
int *bestEdgeNum;

struct edge {
    int tail,head,weight;
};
typedef struct edge edgeType;
edgeType *edgeTab;

int find(int x)
{
    int i,j,root;

    for (i=x;parent[i]!=i; i=parent[i]);
        root=i;
    // path compression
    for (i=x; parent[i]!=i;j=parent[i],parent[i]=root,i=j);
    return root;
}

void makeEquivalent(int i,int j)
{
    if (weight[i]>weight[j])
    {
        parent[j]=i;
        weight[i]+=weight[j];
    }
    else
    {
        parent[i]=j;
        weight[j]+=weight[i];
    }
    numTrees--;
}

int main()
{
    int i,MSTweight=0;
    int root1,root2;
    int usefulEdges;

    cout << "Enter the number of Vertices\n";
    cin >> numVertices;
    cout << "Enter the number of Edges\n";
    cin >> numEdges;

    edgeTab = new edgeType[numEdges];
    parent = new int[numVertices];
    weight = new int[numVertices];
    bestEdgeNum = new int[numVertices];

    if (!edgeTab || !parent || !weight || !bestEdgeNum)
    {
        cout << "error\n";
    }

    cout << "Enter the undirected edge weights for the graph in the format u v w\n";
    for (i=0;i<numEdges;i++)
    {
        cin >> edgeTab[i].tail >> edgeTab[i].head  >> edgeTab[i].weight;
    }
    for (i=0;i<numVertices;i++)
    {
        parent[i]=i;
        weight[i]=1;
    }
    numTrees=numVertices;  // Each vertex is initially in its own subtree
    usefulEdges=numEdges;  // An edge is useful if the two vertices are separate
    while (numTrees>1 && usefulEdges>0)
    {
        for (i=0;i<numVertices;i++)
            bestEdgeNum[i]=(-1);
        usefulEdges=0;
        for (i=0;i<numEdges;i++)
        {
            root1=find(edgeTab[i].tail);
                    root2=find(edgeTab[i].head);
                    if (root1==root2)
                        cout << edgeTab[i].tail <<" , " <<  edgeTab[i].head << " : "
                             << edgeTab[i].weight << " is useless\n";
                    else
                    {
                        usefulEdges++;
                        if (bestEdgeNum[root1] == -1||edgeTab[bestEdgeNum[root1]].weight>edgeTab[i].weight)
                            bestEdgeNum[root1]=i;  // Have a new best edge from this component

            if (bestEdgeNum[root2]==(-1)|| edgeTab[bestEdgeNum[root2]].weight>edgeTab[i].weight)
                bestEdgeNum[root2]=i;  // Have a new best edge from this component
        }
    }
    for (i=0;i<numVertices;i++)
        if (bestEdgeNum[i]!=(-1))
        {
            root1=find(edgeTab[bestEdgeNum[i]].tail);
            root2=find(edgeTab[bestEdgeNum[i]].head);
            if (root1==root2)
                continue;  // This round has already connected these components.
            MSTweight+=edgeTab[bestEdgeNum[i]].weight;
            cout << edgeTab[bestEdgeNum[i]].tail << " " << edgeTab[bestEdgeNum[i]].head << " " << edgeTab[bestEdgeNum[i]].weight << "included in MST\n";
            makeEquivalent(root1,root2);
                    }
                    cout << "numTrees is " << numTrees << endl;

    }
    if (numTrees!=1)
        cout << "MST does not exist\n";
    cout << "Sum of weights of spanning edges is " << MSTweight << endl;

    return 0;
}