#include <iostream>
#include <algorithm>
#include <utility>
#define int long long
#define fu find(now[i].u)
#define fv find(now[i].v)
#define _w now[i].w
#define _col now[i].col
using namespace std;
inline int read()
{
    int ans = 0, f = 0;
    char c = getchar();
    while (!isdigit(c))
        f |= (c == '-'), c = getchar();
    while (isdigit(c))
        ans = (ans << 3) + (ans << 1) + c - 48, c = getchar();
    return f ? -ans : ans;
}
void write(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(48 + x % 10);
}
const int N = 1e5 + 5;
int n, m, need, f[N];
int find(int v)
{
    // cout << "FFF " << v << '\n';
    return f[v] == v ? v : f[v] = find(f[v]);
}
struct edge
{
    int u, v, w, col;
    bool operator<(const edge &x) const
    {
        return w < x.w;
    }
} g[N], now[N];
inline pair<int, int> check(int x)
{
    for (int i = 1; i <= m; ++i)
    {
        now[i] = g[i];
        if (!_col)
            now[i].w += x;
    }
    sort(now + 1, now + m + 1);
    // cout << "FINDDD\n";
    for (int i = 1; i <= n; ++i)
        f[i] = i; //, cout << i << ' ' << f[i] << '\n';
    // cout << x << " KLS " << n << '\n';
    // for (int i = 1; i <= m; ++i)
    //     cout << now[i].u << ' ' << now[i].v << ' ' << _w << ' ' << _col << '\n';
    int ans = 0, cnt = 0;
    for (int i = 1; i <= m; ++i)
        if (fu != fv)
        {
            // int fxx = find(now[i].u);
            // cout << "FFFFXXXXX\n";
            // f[fv] = fxx;
            f[fv] = fu;
            // cout << _col << ' ';
            ans += _w;
            if (!_col)
                ++cnt;
        }
    // cout << '\n'
    //      << x << ' ' << cnt << '\n';
    return {ans, cnt};
}
signed main()
{
    n = read(), m = read(), need = read();
    for (int i = 1; i <= m; ++i)
        g[i] = {read() + 1, read() + 1, read(), read()};
    int l = -200, r = 200, ans = 0;
    while (l <= r)
    {
        int mid = l + r >> 1ll;
        pair<int, int> chk = check(mid);
        if (chk.second >= need)
        {
            // cout << "AA\n";
            l = mid + 1;
            ans = chk.first - mid * need;
        }
        else
            r = mid - 1; //, cout << "BB\n";
    }
    write(ans);
    return 0;
}