RT

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<unordered_map>
#include<vector>
#define x1 xx1
#define y1 yy1
using namespace std;
inline int R(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}return x*f;
}
inline void write(int x){
	if(x<0){x=-x;putchar('-');}
	int y=0;char z[70];
	while(x||!y){z[y++]=x%10+48;x/=10;}
	while(y--)putchar(z[y]);
}
inline void writesp(int x){
	if(x<0){x=-x;putchar('-');}
	int y=0;char z[70];
	while(x||!y){z[y++]=x%10+48;x/=10;}
	while(y--)putchar(z[y]);putchar(32);
}
inline void writeln(int x){
	if(x<0){x=-x;putchar('-');}
	int y=0;char z[70];
	while(x||!y){z[y++]=x%10+48;x/=10;}
	while(y--)putchar(z[y]);putchar(10);
}
inline char read(){
	char ch=getchar();
	while(1) ch=getchar();
	return ch;
}
const int N=5e4+5,M=1e5+5;
struct node{
	int u,v,w,col;
}a[M];
struct edge{
	int u,v,w,col;
}e[M];
int n,m,need,ans;
int f[N];
int getf(int x){
	return f[x]==x?x:f[x]=getf(f[x]);
}
bool cmp(edge x,edge y){
	if(x.w==y.w) return x.col<y.col;
	else return x.w<y.w;
}
int cnt;//白边个数
int sum;//树权值和
int ccnt; 
void kruscal(){
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++){
		int g1=getf(e[i].u),g2=getf(e[i].v);
		if(g1!=g2){
			f[g1]=g2;
			if(!e[i].col) ccnt++;
			sum+=e[i].w;
			ccnt++;
			if(ccnt==n-1) return;
		}
	}
}
void binary_search(int l,int r){
	while(l<=r){
		int mid=l+r>>1;
		for(int i=1;i<=m;i++)
			e[i]=(edge){a[i].u,a[i].v,a[i].col?a[i].w:a[i].w+mid,a[i].col};
		for(int i=1;i<=n;i++) 
			f[i]=i;		
		cnt=ccnt=sum=0;
		kruscal();
		if(cnt>=need) l=mid+1,ans=sum-need*mid;
		else r=mid-1; 
	}
}
int main(){
	n=R(),m=R(),need=R();
	for(int i=1,x,y,z,col;i<=m;i++){
		x=R()+1,y=R()+1,z=R(),col=R();
		a[i]=(node){x,y,z,col};
	}
	binary_search(-100,100);
	write(ans);
}