Submission

Score: 0

User: dddrrrr

Problemset: รัฐบาล

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-12 21:20:27

#include <bits/stdc++.h>
#define int long long
const int MOD = 1e7 + 9;
using namespace std;

int n ,m;
struct DSU{
	vector <int> parent ,sz;
	DSU(int n){
		parent.resize(n);
		sz.resize(n ,0);
		for(int i=0 ;i<n ;i++)parent[i] = i;
	}
	
	int find(int x){
		if(x == parent[x])return x;
		return parent[x] = find(parent[x]);
	}
	
	bool unite(int a ,int b){
		a = find(a);
		b = find(b);
		
		if(a == b)return false;
		if(sz[a] < sz[b])swap(a ,b);
		sz[a] += sz[b];
		parent[b] = a;
		return true;
	}
};


int mst(vector <vector <int>> &edges ,vector <bool>& canuse){
	DSU dsu(n+1);
	int sum = 0 ,cnt = 0;
	for(int i=0 ;i<m ;i++){
		int w=edges[i][0] ,a=edges[i][1] ,b=edges[i][2];
		if(dsu.find(a) != dsu.find(b) && canuse[i]){
			dsu.unite(a ,b);
			cnt ++;		
			sum += w;
		}
	}
	
	//if(cnt == n-1)return LLONG_MAX;	
	return sum;
}

int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m;
	
	vector <vector <int>> edges;
	for(int i=0 ;i<m ;i++){
		int u ,v ,w;
		cin >> u >> v >> w;
		edges.push_back({w ,u ,v});
	}
	
	sort(edges.begin() ,edges.end());
	
	vector <bool> canuse(m ,true);
	vector <int> st;
	
	for(int j=0 ;j<m ;j++){
		canuse[j] = false;
		
		int res = mst(edges ,canuse);
		st.emplace_back(res);
		canuse[j] = true;
	}
	
	sort(st.begin() ,st.end());
	
	int o=2;
	for(int i=0 ;i<st.size()-1 ;i++){
		if(st[i] == st[i+1])continue;
		if(o==0)return 0;
		cout << st[i] << ' ';
		o--;
	}
	return 0;
}