#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,m,nd,l=-101,r=101,ans,sum,cnt,out,fa[maxn];
struct node{int x,y,w,col;};
node a[maxn],tmp[maxn];
bool cmp(node a,node b){return a.w==b.w?a.col<b.col:a.w<b.w;}
int find_set(int x){return x==fa[x]?x:fa[x]=find_set(fa[x]);}
bool check(int k){
	ans=0,sum=0,cnt=0;
	for(int i=1;i<=m;i++) tmp[i]=a[i];
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++) if(!tmp[i].col) tmp[i].w+=k;
	sort(tmp+1,tmp+1+m,cmp);
	for(int i=1;i<=m;i++){
		int x=tmp[i].x,y=tmp[i].y;
		int u=find_set(x),v=find_set(y);
		if(u==v)continue;
		fa[v]=u;
		cnt++;
		if(!tmp[i].col) sum++;
		ans+=tmp[i].w;
		if(cnt==n-1) break;
	}
	return sum>=nd;
}
signed main(){
	ios::sync_with_stdio(false);
	std::cin.tie(0);std::cout.tie(0);
	cin>>n>>m>>nd;
	for(int i=1;i<=m;i++) cin>>a[i].x>>a[i].y>>a[i].w>>a[i].col;
	while(l<r){
		int mid=(l+r)>>1;
		if(check(mid)) l=mid+1,out=ans-nd*mid;
		else r=mid;
	}
	cout<<out<<endl;
	return 0;
}