/*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(){
    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);
}

WA 70pts