Submission

Score: 0

User: hyyh

Problemset: รัฐบาล

Language: cpp

Time: 0.003 second

Submitted On: 2026-01-24 00:14:26

#include <iostream>
#include <math.h>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <iomanip>
#include <set>
#include <bitset>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using piii = tuple<int,int,int>;
using piiii = tuple<int,int,int,int>;
#define endl '\n'
#define f first
#define s second

int const N = 110;

int const N2 = 10010;

vector<piiii> edge;
int DsU[N];
vector<int> ban;

#define int long long

int find(int n){
    if(n == DsU[n]) return n;
    else return DsU[n] = find(DsU[n]);
}


signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    for(int i = 0;i < N;i++) DsU[i] = i;
    int n;cin >> n;
    int m;cin >> m;
    for(int i = 0;i < m;i++){
        int a,b,c;cin >> a>> b >> c;
        edge.emplace_back(c,b,a,i);
    }
    int sum = 0;
    sort(edge.begin(),edge.end());
    for(auto [w,a,b,ind]:edge){
        if(find(a) != find(b)){
            sum += w;
            DsU[find(a)] = find(b);
            ban.emplace_back(ind);
        }
    }
    int ans = 1e9;
    for(auto i:ban){
        int sum2 = 0;
        for(int i = 0;i < N;i++) DsU[i] = i;
        for(auto [w,a,b,ind]:edge){
            if(ind != i && find(a) != find(b)){
                sum2 += w;
                DsU[find(a)] = find(b);
            }
        }
        ans = min(ans,sum2);
    }
    cout << sum << " " << ans;
}