Submission

Score: 0

User: meme_boi2

Problemset: E.Kingdom

Language: cpp

Time: 0.054 second

Submitted On: 2026-03-21 13:05:08

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define tii array<int,3>
vector<int> pa(1e5);
priority_queue<tii> pq;
int find(int i){
    if(pa[i] == i) return pa[i];
    else return pa[i] = find(pa[i]);
}
void U(int u,int v){
    u = find(u); v = find(v);
    if(u < v) pa[v] = u;
    else pa[u] = v;
}
int32_t main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    int n, m, k;
    cin >> n >> m >> k;
    for(int i = 0 ; i < n ; i++){
        pa[i] = i;
    }
    while(m--){
        tii arr;
        cin >> arr[1] >> arr[2] >> arr[0];
        pq.push(arr);
    }
    int ans = 0;
    bool chk = 0; int min_dif= 1e6;
    while(!pq.empty()){
        auto [w,u,v] = pq.top();
        pq.pop();
        if(w >= k){
            U(u,v);
            min_dif = min(min_dif,abs(w-k));
            if(w==k) chk = 1;
            continue;
        }
        
        if(find(u) == find(v)){
            ans += 1;
        //    cout << "Destroy : " << u << ' ' << v << ' ' << 1 << '\n';
        }else{
            ans += min(1 + k, k - w);
            
        //    cout << "Change : " << u << ' ' << v << ' ' << k - w << '\n';
        }
        U(u,v);
       // cout << ans << '\n';
    }
    for(int i = 1; i < n; i++){
     //   cout << find(i) << ' ';
        if(find(i) != find(0)){
            U(i,0);
            chk= 1;
            ans += k;
        }
    }
    if(!chk) ans += min_dif; 
    cout << ans;
}