给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。

题目保证有解。

第一行V,E,need分别表示点数，边数和需要的白色边数。

接下来E行,每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。

一行表示所求生成树的边权和。

V<=50000,E<=100000,所有数据边权为[1,100]中的正整数。

2 2 1

0 1 1 1

0 1 2 0

2

 /**

  * bzoj

  * Problem#2654

  * Accepted

  * Time:1892ms

  * Memory:3052k

  */

 #include<iostream>

 #include<cstdio>

 #include<ctime>

 #include<cctype>

 #include<cstring>

 #include<cstdlib>

 #include<fstream>

 #include<sstream>

 #include<algorithm>

 #include<map>

 #include<set>

 #include<stack>

 #include<queue>

 #include<vector>

 #include<stack>

 #ifndef WIN32

 #define Auto "%lld"

 #else

 #define Auto "%I64d"

 #endif

 using namespace std;

 typedef bool boolean;

 const signed int inf = (signed)((1u << ) - );

 #define smin(a, b) a = min(a, b)

 #define smax(a, b) a = max(a, b)

 #define max3(a, b, c) max(a, max(b, c))

 #define min3(a, b, c) min(a, min(b, c))

 template<typename T>

 inline boolean readInteger(T& u){

     char x;

     int aFlag = ;

     while(!isdigit((x = getchar())) && x != '-' && x != -);

     if(x == -) {

         ungetc(x, stdin);

         return false;

     }

     if(x == '-'){

         x = getchar();

         aFlag = -;

     }

     for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');

     ungetc(x, stdin);

     u *= aFlag;

     return true;

 }

 typedef class union_found{

     public:

         int *f;

         union_found():f(NULL) {}

         union_found(int points) {

             f = new int[(const int)(points + )];

             clear(points);

         }

         int find(int x) {

             if(f[x] != x)    return f[x] = find(f[x]);

             return f[x];

         }

         void unit(int fa, int so) {

             int ffa = find(fa);

             int fso = find(so);

             f[fso] = ffa;

         }

         boolean connected(int a, int b) {

             return find(a) == find(b);

         }

         void clear(int points) {

             for(int i = ; i <= points; i++)

                 f[i] = i;

         }

 }union_found;

 int delta = ;

 typedef class Edge {

     public:

         int from;

         int end;

         int val;

         boolean col;

         inline int getVal() const {

             if(col)    return val + delta;

             return val;

         }

 }Edge;

 boolean operator < (const Edge& a, const Edge& b) {

     return a.getVal() < b.getVal();

 }

 int n, m, lim;

 union_found uf;

 Edge* edge;

 inline void init() {

     readInteger(n);

     readInteger(m);

     readInteger(lim);

     uf = union_found(n);

     edge = new Edge[(const int)(m + )];

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

         readInteger(edge[i].from);

         readInteger(edge[i].end);

         readInteger(edge[i].val);

         readInteger(edge[i].col);

         edge[i].col ^= ;

     }

 }

 int res = ;

 int kruskal(int mid) {

     delta = mid;

     res = ;

     uf.clear(n);

     sort(edge, edge + m);

     int fw = , fin = ;

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

         if(!uf.connected(edge[i].from, edge[i].end)) {

             uf.unit(edge[i].from, edge[i].end);

             fw += edge[i].col, fin ++, res += edge[i].val;

         }

     }

     return fw;

 }

 inline void solve() {

     int l = -, r = , c;

     while(l <= r) {

         int mid = (l + r) >> ;

         if((c = kruskal(mid)) < lim)    r = mid - ;

         else if(c > lim)    l = mid + ;

         else break;

     }

     printf("%d\n", res);

 }

 int main() {

     init();

     solve();

     return ;

 }