题解：
老早看的并没有写
wqs二分的原理和这个凸函数的性质已经证明过了
写的时候
主要的问题在于每次的答案是一个范围
什么意思呢
其实比较简单的做法是
优先取白边，优先取黑边做两次
然后看一下要求的在不在中间就可以了
但是这样有两倍的常数
所以我们换个处理的方法
就是我们优先处理黑边
然后只有答案<=要求的时候更新答案
由于一定有解，所以最后一次更新一定满足要求
代码：
#include <bits/stdc++.h>
using namespace std;
#define IL inline
#define rint register int
#define rep(i,h,t) for (int i=h;i<=t;i++)
#define dep(i,t,h) for(int i=t;i>=h;i--)
char ss[<<],*A=ss,*B=ss;
IL char gc()
{
return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;
}
template<class T>void read(T &x)
{
rint f=,c; while (c=gc(),c<||c>) if (c=='-') f=-; x=c^;
while (c=gc(),<c&&c<) x=(x<<)+(x<<)+(c^); x*=f;
}
const int N=2e5;
struct re{
int a,b,c,d;
}a[N],b[N];
int n,m,k,fa[N],ans;
bool cmp(re x,re y)
{
return(x.c<y.c||((x.c==y.c)&&(x.d>y.d)));
}
int find(int x)
{
return x==fa[x]?x:fa[x]=find(fa[x]);
}
int check(int x)
{
rep(i,,m)
{
if (!a[i].d) b[i].c=a[i].c+x;
else b[i].c=a[i].c;
b[i].a=a[i].a;
b[i].b=a[i].b;
b[i].d=a[i].d;
}
sort(b+,b+m+,cmp);
ans=;
rep(i,,n) fa[i]=i;
int cnt=,cnt2=;
rep(i,,m)
{
int x1=find(b[i].a),x2=find(b[i].b);
if (x1!=x2)
{
if (!b[i].d) cnt2++;
ans+=b[i].c;
fa[x1]=x2;
}
}
return(cnt2);
}
int main()
{
freopen("5.in","r",stdin);
freopen("5.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n>>m>>k;
for(int i=;i<=m;i++)
{
cin>>a[i].a>>a[i].b>>a[i].c>>a[i].d;
a[i].a++; a[i].b++;
}
int h=-,t=;
int ans2=1e8;
while (h<=t)
{
int mid=(h+t)/;
int xx=check(mid);
if (xx>k) h=mid+;
else t=mid-,ans2=ans-mid*k;
}
printf("%d",ans2);
return ;
}