Submission

Score: 0

User: kittipos

Problemset: รัฐบาล

Language: cpp

Time: 0.062 second

Submitted On: 2026-03-05 23:28:17

#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
#include <limits>
#include <tuple>
#include <algorithm>

using namespace std;

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

void set_parent(vector<int> &node, int target_index, int parent_index) {
  if (get_parent(node, target_index) > get_parent(node, parent_index)) {
    swap(target_index, parent_index);
  }
  node[get_parent(node, target_index)] = get_parent(node, parent_index);
}

inline int find_best_path(vector<int> node, const vector<tuple<int, int, int>> &edge, int banded_edge) {
  int sum = 0;
    
  for (int i = 0; i < edge.size(); i++) {
    if (i == banded_edge) continue;

    int src = get<1>(edge[i]);
    int des = get<2>(edge[i]);
    
    if(get_parent(node, src) == get_parent(node, des)) {
      continue;
    }

    int weight = get<0>(edge[i]);
    sum += weight;
    set_parent(node, des, src);
  }

  for (int i = 0; i < node.size()-1; i++) {
    if( get_parent(node, i) != get_parent(node, i+1)) {
      return numeric_limits<int>::max();
    }
  }

  return sum;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;
  
  vector<int> node;
  node.resize(n);
  for (int i = 0; i < n; i++) {
    node[i] = i;
  }

  
  vector<tuple<int, int, int>> edge; // weight source and destination
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;

    
    edge.push_back({c, a, b});
  }
  sort(edge.begin(), edge.end());
  
  int best = find_best_path(node, edge, -1);
  cout << best << ' ';

  int second = numeric_limits<int>::max();
  for (int i = 0; i < m; i++) {
    int better = find_best_path(node, edge, i);
    if (better != best && better < second) {
      second = better;
    }
  }

  cout << second;

  return 0;
}