Submission

[-SSSSSSSSS][-SSSSSSSSSSSSSSSSSSS]

Score: 0

User: ftm

Problemset: E.Kingdom

Language: cpp

Time: 0.029 second

Submitted On: 2025-03-18 03:09:37

#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]);
}

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) {
			u=find(u), v=find(v);
			if(u^v){
				pa[u]=v;
				c++;
			}
			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;
	}
	sort(p.begin(),p.end());
	for(auto e:p){
		int w=e[0],u=e[1],v=e[2];
		u=find(u), v=find(v);
		if(u!=v){
			pa[u]=v;
			c++;
		}
		else{
			ans++;
		}
	}
	ans+=(1ll*k*(n-1-c));
	cout<<ans;
}