#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int n , m , need , ans , anss;
int a[N];
struct node
{
	int x , y , z , col;
}e[N];
bool cmp(node q , node p)
{
	if(q.z == p.z)
		return q.col < p.col;
	return q.z < p.z;
}
int find(int x)
{
	if(a[x] == x)	
		return x;
	return a[x] = find(a[x]);
}
int kruskal()
{
    sort(e + 1 , e + m + 1 , cmp);
	int cnt = 1 , sum = 0;
	for(int i = 1 ; i <= m ; i ++)
	{
		int x = find(e[i].x);
		int y = find(e[i].y);
		if(x != y)
		{
			ans += e[i].z;
			cnt ++;
            if(e[i].col == 0)
                sum ++;
            if(cnt == n)
                break;
			a[x] = y;
		}
        //cout << i << ' ' << e[i].col << endl;
	}
	return sum;
}
signed main()
{
	scanf("%lld%lld%lld" , &n , &m , &need);
	for(int i = 1 ; i <= n ; i ++)
	{
		a[i] = i;
	}	
	for(int i = 1 ; i <= m ; i ++)
	{
		scanf("%lld%lld%lld%lld" , &e[i].x , &e[i].y , &e[i].z , &e[i].col);
        //cout << 111 << endl;
        e[i].x ++ , e[i].y ++;
	}	
    // for(int i = 1 ; i <= m ; i ++)
    // {
    //     cout << e[i].col << endl;
    // }

	//sort(e + 1 , e + m + 1 , cmp);
    //cout << 111 << endl;
    int l = -100 , r = 200;
    while(l <= r)
    {
        int mid = l + r >> 1;
        for(int i = 1 ; i <= m ; i ++)
        {
            if(!e[i].col)
                e[i].z += mid;
        }
        for(int i = 1 ; i <= n ; i ++)
        {
            a[i] = i;
        }
        ans = 0;
        int summ = kruskal();
        //cout << summ << endl;
        if(summ >= need)
        {
            l = mid + 1;
            anss =  ans - summ * mid;
        }
        else    
            r = mid - 1;
        for(int i = 1 ; i <= m ; i ++)
        {
            if(!e[i].col)
                e[i].z -= mid;
        }
    }
    printf("%lld" , anss);
	return 0;
}