#include<bits/stdc++.h> 
using namespace std;
#define pii pair<int,int>
#define mp make_pair
#define se second
#define fi first
inline int read(){
	int x=0,flag=1;char ch=getchar();
	while(ch<'0' || ch>'9'){flag=(ch=='-')?-1:1;ch=getchar();}
	while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*flag;
}
const int N=5e4+10;
const int M=1e5+10;
struct Edge{int u,v,val,newval,kind,num;}edge[M];
bool operator <(const Edge &A,const Edge &B){return (A.newval<B.newval||(A.newval==B.newval&&A.kind==0&&B.kind==1));}
int val=0,fa[N],sz[N];
int get(int u){
	if(fa[u]==u)return u;
	return fa[u]=get(fa[u]);
}
inline void merge(int u,int v){
	u=get(u),v=get(v);
	if(sz[u]<sz[v])swap(u,v);
	fa[v]=u,sz[u]+=sz[v];
}
int pd(int x,int n,int m){
	for(int i=1;i<=m;++i)if(!edge[i].kind)edge[i].newval=edge[i].val+x;
	for(int i=1;i<=n;++i)fa[i]=i,sz[i]=1;
	sort(edge+1,edge+m+1);
	int cnt=0;
	for(int i=1;i<=m;++i){
		if(get(edge[i].u)==get(edge[i].v))continue;
		if(!edge[i].kind)cnt++;
		val+=edge[i].newval;
		merge(edge[i].u,edge[i].v);
//		cerr<<edge[i].u<<' '<<edge[i].v<<'\n';
	}
	return cnt;
}
signed main(){
	int n=read(),m=read(),need=read(),ans;
	for(int i=1;i<=m;++i)edge[i].u=read()+1,edge[i].v=read()+1,edge[i].val=edge[i].newval=read(),edge[i].kind=read(),edge[i].num=i;
	int l=-101,r=101,mid;
	while(l<r){
		for(int i=1;i<=n;++i)fa[i]=i,sz[i]=1;val=0;
		mid=(l+r+1)>>1;int now=pd(mid,n,m);//white +mid
//		cerr<<"st: "<<mid<<' '<<now<<' '<<val<<' '<<l<<' '<<r<<'\n';
		if(now<need)r=mid-1;
		else l=mid,ans=val-need*mid;
	}
	cout<<ans;
	return 0;
}

如果中途不计算 ans，在二分后直接输出 val-need*mid 就会喜提 75tps 好成绩。不懂，求解答。