#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int MAXE = 1e5 + 3, MAXV = 5e4;

struct Edge{
  int u, v, w, col;
}eg[MAXE];

int n, m, need;
int fa[MAXV];

int Getf(int x){
  return fa[x] == x ? x : fa[x] = Getf(fa[x]);
}

pair<int, int> kruskal(int D){
  for(int i = 1; i <= m; i++) eg[i].w += (eg[i].col == 0 ? D : 0);
  for(int i = 1; i <= n; i++) fa[i] = i;
  sort(eg + 1, eg + 1 + m, [](Edge i, Edge j){ return i.w == j.w ? i.col < j.col : i.w < j.w; });
  int ret = 0, sumwight = 0;
  for(int i = 1; i <= m; i++){
    int fx = Getf(eg[i].u), fy = Getf(eg[i].v);
    if(fx != fy){
      fa[fx] = fy;
      sumwight += (eg[i].col == 0);
      ret += eg[i].w;
    }
  }
  ret -= need * D;
  for(int i = 1; i <= m; i++) eg[i].w -= (eg[i].col == 0 ? D : 0);
  return {ret, sumwight};
}

bool as(int D){
  int MIN = kruskal(D).second;
  return MIN >= need;
}

int main(){
  //freopen("P2619_15.in", "r", stdin); 
  cin >> n >> m >> need;
  for(int i = 1; i <= m; i++){
    cin >> eg[i].u >> eg[i].v >> eg[i].w >> eg[i].col;
    eg[i].u++, eg[i].v++;
  }
  int l = -202, r = 202;
  while(l < r){
    int mid = l + (r - l + 1) / 2;
    if(as(mid)){
      l = mid;
    }else{
      r = mid - 1;
    }
  }
  cout << kruskal(l).first;
  return 0;
}