#include<queue>

#include<cmath>

#include<stack>

#include<cstdio>

#include<cctype>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int N=;

const int M=;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

struct node{

    int u,v,w,c;

}e[M];

int n,m,t,tmp,fa[N];

int find(int x){

    if(fa[x]==x)return x;

    return fa[x]=find(fa[x]);

}

inline void unionn(int u,int v){

    fa[u]=v;

}

inline bool cmp(node a,node b){

    return a.w<b.w||(a.w==b.w&&a.c<b.c);

}

void modify(int k){

    for(int i=;i<=m;i++){

        if(!e[i].c)e[i].w+=k;

    }

}

bool pan(int k){

    modify(k);

    sort(e+,e+m+,cmp);

    int num=,cnt=;tmp=;

    for(int i=;i<=n;i++)fa[i]=i;

    for(int i=;i<=m;i++){

        int u=e[i].u,v=e[i].v,w=e[i].w;

        u=find(u),v=find(v);

        if(u!=v){

            unionn(u,v);

            cnt++;tmp+=w;

            if(!e[i].c)num++;

            if(cnt==n-)break;

        }

    }

    modify(-k);

    return num>=t;

}

int solve(int l,int r){

    int ans;

    while(l<r){

        int mid=(l+r+)>>;

        if(!pan(mid))r=mid-;

        else{

            l=mid;

            ans=tmp-mid*t;

        }

    }

    return ans;

}

int main(){

    n=read(),m=read(),t=read();

    for(int i=;i<=m;i++){

        e[i].u=read()+,e[i].v=read()+;

        e[i].w=read(),e[i].c=read();

    }

    printf("%d\n",solve(-,));

    return ;

}