Submission

[-SSSSSSSSS][-SSSSSSSSSSSSSSSSSSS]

Score: 0

User: ftm

Problemset: E.Kingdom

Language: cpp

Time: 0.054 second

Submitted On: 2025-03-17 11:24:33

#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;
	f(i,1,m,1){
		int u,v,w;cin>>u>>v>>w;
		mn=min(mn,w);
		if(w>=k) p.pb({0,u,v});
		else p.pb({k-w,u,v});
	}
	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));
	ans+=(m-c);
	if(mn>k && c==n-1) ans+=mn-k;
	cout<<ans;
}