Submission

[-SSSSSSSSS][-SSSSSSSSSSSSSSSSSSS]

Score: 0

User: KotatsuCat

Problemset: E.Kingdom

Language: cpp

Time: 0.051 second

Submitted On: 2025-01-07 22:43:48

#include<bits/stdc++.h>
#define ll long long
#define tpi tuple<ll,int,int>

using namespace std;

const int mxN = 1e5+1;
int pa[mxN];
vector<tpi> edges;

int fp(int x){
	if(pa[x]==x) return x;
	return pa[x]=fp(pa[x]);
}

int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	int n,m,k;
	cin >> n >> m >> k;
	for(int i=0;i<m;i++){
		int u,v,w;
		cin >> u >> v >> w;
		if(w<k) w = k-w;
		else w = 0;
		edges.emplace_back(w, u, v);
	}
	sort(edges.begin(), edges.end());
	iota(pa, pa+n, 0);
	ll ans = 0;
	for(auto &[w, u, v]:edges){
		int pu = fp(u), pv = fp(v);
		if(pu==pv){
			ans++;
			continue;
		}
		pa[pv]=pu;
		--n;
		ans+=w;
	}
	ans+=1ll*(n-1)*k;
	cout << ans;

	return 0;
}