P2619 如题

/*                                                                                
                      Keyblinds Guide
     				###################
      @Ntsc 2024

      - Ctrl+Alt+G then P : Enter luogu problem details
      - Ctrl+Alt+B : Run all cases in CPH
      - ctrl+D : choose this and dump to the next
      - ctrl+Shift+L : choose all like this
      - ctrl+K then ctrl+W: close all
      - Alt+la/ra : move mouse to pre/nxt pos'
	  
*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;

#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first

// #define innt int
#define itn int
// #define inr intw
// #define mian main
// #define iont int

#define rd read()
int read(){
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
		if (ch == '-')
			ff = -1;
		ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
      xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
void write(int out) {
	if (out < 0)
		putchar('-'), out = -out;
	if (out > 9)
		write(out / 10);
	putchar(out % 10 + '0');
}

#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
	if constexpr (enable_dbg){
    cerr << s;
    if(1)cerr<<' ';
		if constexpr (sizeof...(Args))
			dbg(args...);
	}
}

#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif


const int N = 5e5 + 5;
const int INF = 1e3;
const int M = 1e7;
const int MOD = 1e9 + 7;



struct edge{
    int a,b,c,col;
}e[N];

int t;
int n,m,K;
bool cmp(edge a,edge b){
    if(a.c+t*(a.col==0)==b.c+t*(b.col==0))return a.col==0;
    return a.c+t*(a.col==0)<b.c+t*(b.col==0);
}


int fa[N];

int find(int x){
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}



pii kruskal(bool flg=0){
    int sum=0,cnt=0;
    sort(e+1,e+m+1,cmp);//不稳定排序！
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        if(flg&&cnt==K&&e[i].col==0)continue;
        int faa=find(e[i].a),fbb=find(e[i].b);
        if(faa==fbb)continue;
        fa[faa]=fbb;
        sum+=e[i].c+t*(e[i].col==0);
        if(!e[i].col)cnt++;
    }
    return mp(sum,cnt);
}


int work(){
    int l=-INF,r=INF;
    int res=0;
    while(l<=r){
        // itn mid=l+r>>1;
        // t=mid;
        // if(kruskal().ps>=K)l=mid+1,res=mid;
        // else r=mid-1;
        int mid=(l+r)>>1;
		t=mid;
		
		auto tp=kruskal();
		if(tp.ps>=K){
			l=mid+1;
			res=tp.pf-K*mid;//更新答案
		}
		else r=mid-1;
		// for(int i=1;i<=m;i++)
		// 	if(e[i].c==0)
		// 		e[i].v-=mid;//最终要把加上的减掉
    }
    // cdbg(res,kruskal().ps);
    // while(kruskal().ps<K){res--;t=res;cdbg(res,kruskal().ps);}
    // while(kruskal().ps>K){res++;t=res;cdbg(res,kruskal().ps);}
    // cdbg(res,kruskal().ps);
    return res;
}

void solve(){
     n=rd,m=rd,K=rd;
    for(int i=1;i<=m;i++){
        int a=rd+1,b=rd+1,c=rd,col=rd;
        e[i]={a,b,c,col};
    }

    auto res=kruskal();
    
    // if(res.ps==K)cout<<res.pf<<endl;
    // else {
        t=work();
        cout<<t<<endl;
        // res=kruskal(1);
        // cdbg(res.pf,res.ps);
        // cout<<res.pf-res.ps*t<<endl;
    // }
}

signed main() {
    // freopen("center.in","r",stdin);
    // freopen("center.out","w",stdout);

    int T=1;
    while(T--){
    	solve();
    }
    return 0;
}