Submission

Score: 0

User: Nathako9n

Problemset: E.Kingdom

Language: cpp

Time: 0.051 second

Submitted On: 2026-01-02 07:26:44

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
#define pii pair<int,int>
using namespace std;
const int N = 1e5+5;
int n,k,m;
int he[N+2];
int fh(int x){
    if(he[x]==x)return x;
    return he[x]=fh(he[x]);
}
void uh(int x,int y){
    x=fh(x);
    y=fh(y);
    if(x==y)return;
    he[x]=y;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>k;
    int cnt=n;
    for(int i=1;i<=n;i++){
        he[i]=i;
    }
    vector<tuple<int,int,int>> ed;
    for(int i=1;i<=m;i++){
        int u,v,w;cin>>u>>v>>w;

        if(w>=k){uh(u,v);cnt--;}
        else{
            ed.emplace_back(k-w,u,v);
         //   cout<<u<<" " <<v<<" "<<w<<endl;
        }
    }
    sort(ed.begin(),ed.end());
    ll ans=0;

    for(auto[c,x,y]:ed){
    //    cout<<c<<" " <<x <<" "<<y<<endl;
        if(fh(x)!=fh(y)){
            uh(x,y); ans+=c;cnt--;
           // cout<<c<<" " <<x<<" " <<y<<endl;
        }
        else{
            ans++;
        }
    }
    //cout<<ans<<endl;
    cnt--;
    ans+=cnt*k;
    cout<<ans;
    return 0;
}
/*

0 1 2
0 2 3
1 2 4
1 3 5
1 1 3
3 0 2

*/