用的prim,#12Wa了

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
//#define int long long
using namespace std;
const int N = 101000, M = 1000010;

/*
4 4 1
0 1 5 1
0 2 1 0
1 3 1 0
2 3 3 1
*/
struct Edge {
	int v, next, col, mid = 0;
	int w;
} e[M];

int n, m, head[N], bian;

void adde(int u, int v, int w, int color) {
	e[++bian].v = v;
	e[bian].col = color;
	e[bian].w = w;
	e[bian].next = head[u];
	head[u] = bian;
}

struct Sab {
	int u, d;
};

bool operator<(const Sab &x, const Sab &y) {
	return x.d > y.d;
}


priority_queue<Sab> q;
int dis[N];
int Tdis[N];
bool vis[N];
int lasts[M];

int res = 0, cnt = 0, k = 0;

int prim(int noon) {
	for (int i = 1; i <= bian; i++) {
		if (e[i].col == 0) {
			e[i].mid = noon;
		}
	}
	memset(lasts, 0x3f, sizeof(lasts));
	memset(dis, 0x3f, sizeof(dis));
	memset(Tdis, 0x3f, sizeof(Tdis));
	memset(vis, 0, sizeof(vis));
	res = 0, cnt = 0;
	while (!q.empty())
		q.pop();

	dis[1] = 0;
	q.push({1, 0});
	while (!q.empty()) {
		if (cnt >= n) {
			break;
		}
		int u = q.top().u;
		int d = q.top().d;
		q.pop();
		if (vis[u]) {
			continue;
		}
		vis[u] = 1;
		cnt++;
		res += d;
		for (int i = head[u]; i; i = e[i].next) {
			//cout << "正在遍历边" << u << "-->" << e[i].v << " " << e[i].w + e[i].mid << endl;
			int To = e[i].v, wei = e[i].w + e[i].mid ;
			if ((wei < dis[To] || (wei == dis[To] && e[i].col == 0 && !(lasts[i]!=0x3f3f3f3f && e[i].col==0))) && vis[To] != 1) {
				//cout << "更新了边" << u << "-->" << e[i].v << " " << e[i].w + e[i].mid << endl;
				lasts[To] = i;
				dis[To] = wei;
				Tdis[To] = e[i].w;
				q.push({To, wei});
			}
		}
	}
	int total = 0;
	for (int i = 1; i <= n; i++) {
		if (lasts[i] != 0x3f3f3f3f && e[lasts[i]].col == 0) {
			total++;
		}
	}
	//cout << total << " " << noon << endl;
	return total;
}

signed main() {

	cin >> n >> m >> k;
	for (int i = 1; i <= m; ++i) {
		int a, b, d;
		int c;

		cin >> a >> b >> c >> d;
		a++;
		b++;
		adde(a, b, c, d);
		adde(b, a, c, d);
	}
	int lef = -111, righ = 111, anss = 0;
	while (lef <= righ) {
		int middle = (lef + righ) / 2;
		int coun = prim(middle);
		if (coun >= k) {
			anss = 0;
			for (int i = 1; i <= n; i++) {
				if (dis[i] != 0x3f3f3f3f) {
					anss += dis[i];
				}
			}
      anss=anss-k*middle;
			lef = middle+1;

		} else {
			righ = middle - 1;
		}
	}
	cout << anss << endl;
	return 0;
}