#include <bits/stdc++.h>
using namespace std;
const int N=50005,M=100005;
int fa[N],n,m,need;
struct edge{int u,v,w,c;}e[M];
bool CMP(edge a,edge b){return (a.w==b.w)? a.c<b.c:a.w<b.w;}
inline int findfa(int x){return (fa[x]==x)? x: fa[x]=findfa(fa[x]);}
int sum,ans,temp,cnt=0;
int main()
{
	scanf("%d%d%d",&n,&m,&need);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].w,&e[i].c);
		e[i].u++;e[i].v++; 
	}
	int l=-114,r=114;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		for(int i=1;i<=m;i++)if(e[i].c==0)e[i].w+=mid;
		for(int i=1;i<=n+1;i++)fa[i]=i;
		sum=0,cnt=0,temp=0;
		sort(e+1,e+1+m,CMP);
		for(int i=1;cnt!=n-1;i++)
		{
			int xx=findfa(e[i].u),yy=findfa(e[i].v);
			if(xx!=yy){
				cnt++;
				fa[xx]=yy;
				if(e[i].c==0) temp++;
				sum+=e[i].w;
			} 
		}
		if(temp>=need)l=mid+1,ans=sum-need*mid;
		else          r=mid-1;
		for(int i=1;i<=m;i++)if(e[i].c==0)e[i].w-=mid;
	}
	printf("%d",ans);
	return 0;
}