Submission

[-SSSSSSSSS][-SSSSSSSSSSSSSSSSSSS]

Score: 0

User: ftm

Problemset: E.Kingdom

Language: cpp

Time: 0.032 second

Submitted On: 2025-03-17 13:20:01

#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b,c) for(int i=a;i<=b;i+=c)
#define r(i,a,b,c) for(int i=a;i>=b;i-=c)
#define fi first
#define se second
#define pb push_back
using ll=long long int;
using pii=pair<int,int>;
const int N=1e5+5;
const int M=1e9+7;
int pa[N];
ll c;
ll ans=0;
vector<array<int,3>> p;

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

void uset(int a, int b, int w){
	a=find(a), b=find(b);
	if(a==b) return;
	pa[b]=a;
	c++;
	ans+=w;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int n,m,k;cin>>n>>m>>k;
	f(i,1,n,1) pa[i]=i;
	int mn=1e9,mx=-1000000000;
	f(i,1,m,1){
		int u,v,w;cin>>u>>v>>w;
		if(w>=k) {
			uset(u,v,0);
			mn=min(mn,w);
		}
		else {
			p.pb({k-w,u,v});
			mx=max(mx,w);
		}
	}
	if(c==n-1){
		if(p.size()) ans+=min(mn-k,k/*add new k road*/);
		else ans+=min(mn-k,k-mx-1/*-1 don't destroy mx road'*/);
		ans+=p.size();
		cout<<ans;
		return 0;
	}
	int cnt=0;
	sort(p.begin(),p.end());
	for(auto e:p){
		int w=e[0],u=e[1],v=e[2];
		uset(u,v,w);
	}
	ans+=(1ll*k*(n-1-c));
	cout<<ans;
}