Submission

Score: 100

User: krittaphot

Problemset: รัฐบาล

Language: cpp

Time: 0.007 second

Submitted On: 2026-03-06 23:05:53

#include <bits/stdc++.h>

using namespace std;

int find_parent(int node,vector<int> &parent){
	if(parent[node] == node){
		return node;
	}
	return parent[node] = find_parent(parent[node],parent);
}

int dfs(int start,int stop,vector<vector<pair<int,int>>> &adj,int mx,int parent){
	if(start == stop){
		return mx;
	}
	for(int i = 0;i<adj[start].size();i++){
		int v = adj[start][i].first;
		int w = adj[start][i].second;
		if(v == parent) continue;
		int res = dfs(v,stop,adj,max(mx,w),start);
		if(res != -1) return res;
	}
	
	return -1;
	
}

int main()
{
	int n,m;
	cin >> n >> m;
	vector<pair<int,pair<int,int>>> edges;
	vector<vector<pair<int,int>>> adj(n+1);
	vector<int> use(m,0);
	vector<int> parent(n+1);
	for(int i = 0;i<=n;i++){
		parent[i] = i;
	}
	for(int i = 0;i<m;i++){
		int a,b,w;
		cin >> a >> b >> w;
		edges.push_back({w,{a,b}});
	}
	
	sort(edges.begin(),edges.end());
	
	int sum = 0;
	for(int i = 0;i<m;i++){
		int cost = edges[i].first;
		int a = edges[i].second.first;
		int b = edges[i].second.second;
		int A = find_parent(a,parent);
		int B = find_parent(b,parent);
		if(A != B){
			sum += cost;
			parent[A] = B;
			adj[a].push_back({b,cost});
			adj[b].push_back({a,cost});
			use[i] = 1;
		}
	}
	int diff = INT_MAX;
	for(int i = 0;i<m;i++){
		if(!use[i]){
			int cost = edges[i].first;
			int a = edges[i].second.first;
			int b = edges[i].second.second;
			int mx = dfs(a,b,adj,-1,-1);
			diff = min(diff,cost - mx);
		}
	}
	
	cout << sum << " " << sum+diff;
	
	
//	cout << sum;
	
	
}