Submission

Score: 100

User: boomm

Problemset: รัฐบาล

Language: cpp

Time: 0.004 second

Submitted On: 2026-03-13 21:09:51

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

int parent[100005];
int find(int i){
	if(parent[i]==i) return i;
	return parent[i]=find(parent[i]);
}
void unite(int a,int b){
	a=find(a);
	b=find(b);
	if(a!=b) parent[b]=a;
}

int main(){
	ios_base::sync_with_stdio(0);
	int n,m;
	cin >> n >> m;
	vector<vector<int>> v(m,vector<int>(3));
	vector<int> inmst;
	for(int i=0;i<m;i++){
		cin >> v[i][0] >> v[i][1] >> v[i][2];
	}
	for(int i=1;i<=n;i++){
		parent[i]=i;
	}
	sort(v.begin(),v.end(),[](const vector<int> &a,const vector<int> &b){
		return a[2] < b[2];
	});
	int ans=0;
	for(int i=0;i<m;i++){
		int u=v[i][0];
		int x=v[i][1];
		int w=v[i][2];
		if(find(u) != find(x)){
			unite(u,x);
			inmst.push_back(i);
			ans+=w;
		}
	}
	int mn=1e9;
	cout << ans << " ";
	for(int k=0;k<inmst.size();k++){
		int answer=0;
		int c=0;
		for(int i=1;i<=n;i++){
			parent[i]=i;
		}
		for(int i=0;i<m;i++){
			int u=v[i][0];
			int x=v[i][1];
			int w=v[i][2];
			if(inmst[k]==i) continue;
			if(find(u) != find(x)){
				unite(u,x);
				answer+=w;
				c++;
			}
		}
		if(c==n-1) mn=min(mn,answer);
	}
	cout << mn;
	
	return 0;
}