码风很丑。。。 别的好像都是将白的边加上某个值，我的是将黑边加，感觉问题不大，然后kruskal统计答案的时候，排序优先选白边，直接加上边原来的权值就行。 下了一下第 6 个数据点，发现当最终二分到 mid=-8 时 ans=22395，sum=365；当 mid=- 9时 ans=22443，sum = 359 。而答案却是 362 , 22419.。。。。

#include<bits/stdc++.h>
using namespace std;
int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c-'0'),c=getchar();
	return x*f;
}
const int MAXN=1e5+10,inf=100;
int n,m,need,mid,l,r,ans,out;
int f[MAXN];
struct node
{
	int u,v,val,p;
}d[MAXN];
bool cmp(node x,node y)
{
	if(x.val+x.p*mid==y.val+y.p*mid)return x.p<y.p;
	return x.val+x.p*mid<y.val+y.p*mid;
}
int cz(int x)
{
	if(f[x]==x)return x;
	return f[x]=cz(f[x]);
}
void hb(int x,int y)
{
	int a=cz(x),b=cz(y);
	f[a]=b; 
}
bool pd()
{
	int sum=0,cnt=n;
	ans=0;
	sort(d+1,d+1+m,cmp);
	for(int i=0;i<=n-1;i++)
	f[i]=i;
	for(int i=1;cnt>1&&i<=m;i++)
	{
		if(cz(d[i].u)!=cz(d[i].v))
		{
			hb(d[i].u,d[i].v);
			sum+=(d[i].p==0);
			cnt--;
			ans+=d[i].val;
		}
	}
	if(sum<=need)return 1;
	return 0;
}
int main()
{
	n=read();
	m=read();
	need=read();
	for(int i=1;i<=m;i++)
	{
		d[i].u=read();
		d[i].v=read();
		d[i].val=read();
		d[i].p=read(); 
	}
	l=-inf,r=inf;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(pd())out=ans,l=mid+1;
		else r=mid-1;
	}
	printf("%d\n",out);
 	return 0;
}