Submission

Score: 100

User: nemuchannnUwU

Problemset: รัฐบาล

Language: cpp

Time: 0.004 second

Submitted On: 2026-03-13 16:49:43

#include<bits/stdc++.h>
using namespace std;
vector<int> parent;
int find(int x){
	if (parent[x]==x) return x;
	return parent[x]=find(parent[x]);
}

bool unite(int u,int v){
	u=find(u);
	v=find(v);
	if (u==v) return false;
	parent[u]=v;
	return true;;
}
int main(){
	cin.tie(nullptr)->sync_with_stdio(0);
	int n,m; cin >> n >> m;
	parent=vector<int> (n+1);
	for (int i=1;i<=n;i++){
		parent[i]=i;
	}
	
	vector<vector<int>> edges(m+1,vector<int> (3));
	for (int i=1;i<=m;i++){
		cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
	}
	sort(edges.begin(),edges.end(),[](const vector<int> &a,const vector<int> &b){
		return a[2]<b[2];
	});
	
	int first=0;
	vector<int> used;
	for (int i=1;i<=m;i++){
		int u=edges[i][0];
		int v=edges[i][1];
		int w=edges[i][2];
		if (unite(u,v)){
			first+=w;
			used.push_back(i);
		}
	}
	int second=INT_MAX;
	for (int ban : used){
		for (int i=1;i<=n;i++){
			parent[i]=i;
		}
		int cnt=0;
		int temp=0;
		for (int i=1;i<=m;i++){
			if (ban==i) continue;
			int u=edges[i][0];
			int v=edges[i][1];
			int w=edges[i][2];
			if (unite(u,v)){
				temp+=w;
				cnt++;
			}
		}
		if (cnt==n-1) second=min(second,temp);
	}
	cout << first << " " << second;
}