Submission

Score: 0

User: NovemNotes

Problemset: รัฐบาล

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-12 12:46:48

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

const int N = 109;

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

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

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin >> n >> m;v.resize(m);
    for(int i=1;i<=n;i++)head[i]=i;
    for(auto &[a,b,c]:v)cin >> a >> b >> c;
    sort(v.begin(),v.end(),[](const auto &a,const auto &b){
        return get<2>(a) < get<2>(b);
    });
    tmp=v;
    for(auto &[from,to,w]:v){
        int ha = findhead(from);
        int hb = findhead(to);
        if(ha==hb)continue;
        head[ha] = hb;
        ans1+=w;
        use.emplace_back(from,to,w);
    }
    int sz = use.size();
    int f = get<0>(use[sz-1]);
    int t = get<1>(use[sz-1]);
    int wt = get<2>(use[sz-1]);
    for(int i=1;i<=n;i++)head[i]=i;
    for(auto &[from,to,w]:tmp){
        if(from==f&&to==t&&wt==w)continue;
        int ha = findhead(from);
        int hb = findhead(to);
        if(ha==hb)continue;
        head[ha] = hb;
        ans2+=w;
    }
    cout << ans1 << " " << ans2 << "\n";
    return 0;
}