Submission

Score: 0

User: C12

Problemset: รัฐบาล

Language: cpp

Time: 0.002 second

Submitted On: 2026-01-21 16:18:01

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pii pair<ll,ll>
#define puii pair<ull,ull>
#define piii pair<ll,pii>
#define ll long long
#define ull unsigned long long
#define mp make_pair
 
#define mpiii(a,b,c) make_pair(a,make_pair(b,c));
int32_t mod = 1e9+7;

int p[101];
ll n,m,u,v,w;
vector<piii>edge;
piii x;
ll sum;
int check[10000];

int dsu(int i){
    // cout << i << ' ' << p[i] << ' ' << (p[i] == i) << '\n';
    if(p[i] == i) return i;

    p[i] = dsu(p[i]);
    return p[i];
}

ll mst(int k){
    sum = 0;

    for(int i = 1;i <= n;i++){
        p[i] = i;    
    }

    if(k != -1){
        x = edge[k];
        w = x.f;
        u = x.s.f;
        v = x.s.s;
        p[dsu(u)] = p[v];

        sum += w;
    }

    for(int i = 0;i < m;i++){
        // if(i == k) continue;
        x = edge[i];
        w = x.f;
        u = x.s.f;
        v = x.s.s;
        // cout << u << ' ' << dsu(u) << ' ' << v << ' ' << dsu(v) << '\n';
        if(dsu(u) != dsu(v)){
            sum += w;
            if(k == -1){
                check[i] = 0;
            }
            p[dsu(u)] = p[v];
        }
    }

    for(int i = 1;i <= n;i++){
        if(dsu(1) != dsu(i)) {
            // cout << "FALSE\n";
            return LLONG_MAX;
        }
    }
    // cout << k << ' ' << sum << '\n';
    return sum;
}

void solve(){
    cin >> n >> m;

    for(int i = 0;i < m;i++){
        cin >> u >> v >> w;
        edge.push_back(mp(w,mp(u,v)));
    }

    for(int i = 0;i < m;i++){
        check[i] = 1;
    }

    sort(edge.begin(),edge.end());

    ll main_ans = mst(-1);
    ll sec_ans = LLONG_MAX;
    for(int i = 0;i < m;i++){
        if(check[i]){
            sec_ans = min(sec_ans,mst(i));
        }
    }

    cout << main_ans << '\n' << sec_ans;

    return;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    // ll q;
 
    // cin >> q;
    
    // while(q--) 
    solve();

    return 0;
}
/*

5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66

*/