朴素最小生成树，kruskal算法，先按照必选在前，低费在前的原则进行排序，再把必修边全都加进去。

我们用k存储还没有找到祖先的边的数量，用f[x]存储x的祖先。易知只有当k==1时结束，程序输出。

如果祖先不同，加边的时候就修改祖宗相同，并k--。

对于选修边，如果祖先相同就不考虑，否则考虑。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define db double
#define Dg(n)  cout<<n<<endl;
#define F(n) for(int i=1;i<=n;i++)
#define F1(n) for(int i=n;i>=1;i--)
#define F2(n,s) for(int i=1;i<=n;i+=s)
#define F4(n,m) for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
#define FD(name,n) for(int name=1;name<=n;name++)
#define li i&-i
#define nel (rt<<1)
#define ner (rt<<1|1)
#define trm ((tr[rt].l+tr[rt].r)>>1)
#define trf ((tr[rt].r-tr[rt].l))
#define op(a,type) bool operator a (const type &an)

const int dx[5]={0,1,-1,0,0};
const int dy[5]={0,0,0,1,-1};
const int INF=0x3f3f3f3f;
const int LXB=2e5+10;
const db e=2.718281828459;
const db pai=3.1415926535;
const int lxb=3e3;

int n,m,k;
int f[LXB];
int mp[lxb][lxb];
string s;
char p;

struct node{
   int l,r,x,t;
   op(<,node){return t==an.t?x<an.x:t<an.t;} //可以用cmp代替

}no[LXB];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}//寻找祖先，路径压缩

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int T=1;
    while(T--){
        cin>>n>>m;
        F(m){cin>>no[i].t>>no[i].l>>no[i].r>>no[i].x;}
        sort(no+1,no+1+m);//排序
        int z=0;
        F(n){f[i]=i;}k=n;
        int ans=0;
        while(no[++z].t==1){
            int fx=find(no[z].l),fy=find(no[z].r);
            if(fx!=fy)k--,f[fx]=fy;
            ans+=no[z].x;
        }//加入必修边
        z--;
        while(k>1 and ++z<=m){
            int fx=find(no[z].l),fy=find(no[z].r);
            if(fx!=fy)k--,f[fx]=fy,ans+=no[z].x;
        }//加选修边
        cout<<ans;
    }
    return 0;//为美好的世界献上return 0
}