struct DisjointSetUnion
{
    static const int __=10005;
    int pre[__];
    DisjointSetUnion() {memset(pre,-1,sizeof(pre));}
    void un(int x,int y)
    {
        x=fd(x),y=fd(y);
        if(x==y)return;
        if(pre[x]<pre[y])
            pre[x]+=pre[y],pre[y]=x;
        else
            pre[y]+=pre[x],pre[x]=y;
    }
    int fd(int x)
    {
        if(pre[x]<0)return x;
        return pre[x]=fd(pre[x]);
    }
    void clear(){memset(pre,-1,sizeof(pre));}
}dsu;

Kruskal

struct Kruskal
{
    static const int __=100005;
    int edge_num;
    struct edge
    {
        int x,y,z;
        bool operator<(const edge& b)const
        {
            return z<b.z;
        }
        void set(int _x,int _y,int _z)
        {
            x=_x,y=_y,z=_z;
        }
    }e[__*2];

    //并查集板子

    void scan()
    {
        fup(i,1,edge_num)
        {
            int x,y,z;
            sf("%d%d%d",&x,&y,&z);
            e[i].set(x,y,z);
        }
    }

    void solve()
    {
        sort(e+1,e+edge_num+1);
        fup(i,1,edge_num)
        {
            if(dsu.fd(e[i].x)!=dsu.fd(e[i].y))
            {
                lca.add_edge(e[i].x,e[i].y,e[i].z);
                lca.add_edge(e[i].y,e[i].x,e[i].z);
                dsu.un(e[i].x,e[i].y);
            }
        }
    }

    void clear(){mem(dsu.pre,-1);}
}M;

struct mst
{
    static const int _n_=1005,_e_=1000005;
    struct edge
    {
        int nex,dis,nex_edge;
        edge() {}
        edge(int x,int y,int z=0):
            nex(x),dis(y),nex_edge(z) {}
        bool operator<(const edge& b)const
        {
            return dis>b.dis;
        }
    }e[_e_<<1];
    int head[_n_],dis[_n_],ne;
    bool vis[_n_];
    mst():ne(0){memset(head,-1,sizeof(head));}
    void add_edge(int x,int y,int dis)
    {
        e[ne]=edge(y,dis,head[x]);
        head[x]=ne++;
    }
    int prim()
    {
        int sum=0;
        memset(vis,false,sizeof(vis));
        memset(dis,0x3f3f3f3f,sizeof(dis));
        priority_queue<edge>Q;
        dis[1]=0,Q.push(edge(1,0));
        while(!Q.empty())
        {
            edge t=Q.top();
            Q.pop();
            if(vis[t.nex])continue;
            sum+=t.dis;
            vis[t.nex]=true;
            for(int i=head[t.nex];~i;i=e[i].nex_edge)
                if(!vis[e[i].nex] && e[i].dis<dis[e[i].nex])
                {
                    dis[e[i].nex]=e[i].dis;
                    Q.push(edge(e[i].nex,e[i].dis));
                }
        }
        return sum;
    }
    void clear(){ne=0,memset(head,-1,sizeof(head));}
}prim;