Submission

Score: 0

User: NovemNotes

Problemset: รัฐบาล

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-12 13:50:43

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

#define int long long
const int N = 109;
const int INF = 1e18;

int n,m;
int ans1=0,ans2=INF;
int head[N];
vector<tuple<int,int,int>> edge;
vector<tuple<int,int,int>> use;

void reset(){
    for(int i=1;i<N;i++)head[i]=i;
}

int findhead(int n){
    return (head[n]==n? n : head[n] = findhead(head[n]));
}

int check(int f,int t,int wt){
    int sum=0;
    reset();
    for(auto [from,to,w] : edge){
        if(from==f && t==to && w==wt)continue;
        int ha = findhead(from),hb = findhead(to);
        if(head[ha]==head[hb])continue;
        head[ha]=hb;
        sum+=w;
    }
    return sum;
}

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin >> n >> m;reset();
    for(int i=0;i<m;i++){
        int a,b,c;cin >> a >> b >> c;
        edge.emplace_back(a,b,c);
    }
    sort(edge.begin(),edge.end(),[](const auto &a,const auto &b){
        return get<2>(a) < get<2>(b);
    });
    for(auto &[from,to,w]:edge){
        int ha = findhead(from),hb = findhead(to);
        if(head[ha]==head[hb])continue;
        ans1+=w;
        head[ha]=hb;
        use.emplace_back(from,to,w);
    }
    for(auto [from,to,w] : use){
        ans2=min(ans2,check(from,to,w));
    }
    cout << ans1 << " " << ans2 << "\n";
    return 0;
}