/*YYC is Thinking Here*/
#include<bits/stdc++.h>
#define deb(var) cerr<<#var<<'='<<var<<'\n'
#define pii pair<int,int>
#define tpiiii tuple<int,int,int,int>
using namespace std;
const int maxn = 2e5+10,inf = 0x3f3f3f3f,maxc = 100;
int n,m,s,t,u,v,c,col,lim,fa[maxn],rk[maxn],cnta,cntb;
int getfa(int u) { return fa[u] == u ? u : fa[u] = getfa(fa[u]); }

tpiiii ea[maxn],eb[maxn],ec[maxn];
inline void addedge(int u,int v,int c,bool col) { (!col?ea[++cnta]:eb[++cntb]) = tpiiii{c,u,v,!col}; }
inline pii krust() {
	int ans = 0,cnt = 0;
	for(int i = 1;i<=n+2;++i) fa[i] = i,rk[i] = 1;
	for(int w,u,v,c,i = 1;i<=m;++i) {
		tie(w,u,v,c) = ec[i];
		int ufa = getfa(u),vfa = getfa(v);
		if(ufa == vfa) continue;
		if(rk[ufa] > rk[vfa]) swap(u,v);
		fa[ufa] = vfa, rk[vfa] += rk[ufa];
		cnt += c; ans += w;
	}
	return {cnt,ans};
}
inline void merge(int k) {
	int i = 1,j = 1;
	for(int p = 1;p<=m;++p) {
		int aw = get<0>(ea[i]),
			bw = get<0>(eb[j]);
		if(aw + k <= bw) ec[p] = ea[i++];
		else ec[p] = eb[j++];
	}
}
signed main(){
//	freopen("E:\\Users\\23282\\Downloads\\P2619_6.in","r",stdin);
	cin>>n>>m>>lim;
	for(int i = 1;i<=m;++i) {
		cin>>s>>t>>c>>col;
		++s,++t;
		addedge(s,t,c,col);
	}
	ea[++cnta] = eb[++cntb] = tpiiii{inf,inf,inf,inf};
	sort(ea+1,ea+cnta+1),sort(eb+1,eb+cntb+1);
	int l = -maxc,r = maxc,cnt,ans,mid;
	while(l < r) {
		mid = l + r + 1 >> 1;
		merge(mid);
		tie(cnt,ans) = krust();
		if(cnt <= lim) r = mid - 1;
		else l = mid;
	}
	cout<<ans + mid*(cnt-lim);
}

错哪里了？