template<typename T,size_t V,size_t E>
struct Kruskal
{
    typedef tuple<T,int,int> Edge;
    typedef pair<T,int> PTI;
    Edge edges[E];
    int inmst[E];
    int n; // number of vertex
    int m; // number of edge
    int uf[V];
    int find(int x)
    { return x==uf[x]?x:uf[x]=find(uf[x]); }
    void init(int n_) { n=n_; m=0; }
    void addedge(int u,int v,T w)
    { edges[m++]={w,u,v}; }

    PTI solve()
    {
        int cnt=n; // number of connected component
        T sum=0;
        int u,v; T w;
        for(int i=0;i<n;i++) uf[i]=i;
        sort(edges,edges+m);
        for(int i=0;i<m&&cnt>1;i++)
        {
            tie(w,u,v)=edges[i];
            u=find(u); v=find(v);
            if(u==v) continue;
            inmst[i]=1; sum=sum+w;
            cnt--; uf[u]=v;
        }
        return {sum,cnt==1}; // {totval in mst, ismst}
    }
};