记录编号	605015	评测结果	AAAAAAAAAA
题目名称	2453.次小生成树	最终得分	100
用户昵称	OTTF	是否通过	通过
代码语言	C++	运行时间	0.695 s
提交时间	2025-08-13 13:51:18	内存使用	13.07 MiB

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <numeric>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

constexpr int N = 114514;
constexpr int LOG = 19;

class UnionFind {
	private:
	int count;
	vector<int> father;
	vector<int> size {};

	public:

	UnionFind (int n = 1e5);
	int find (int num);
	bool same (int one, int two) {return find (one) == find (two);}
	void merge (int one, int two);
	int howmany () {return count;}
};

UnionFind::UnionFind (int n) {
	father.resize(n);
	size.resize(n);
	count = n;

	iota (father.begin(), father.end(), 0);
}

int UnionFind::find (int num) {
	vector<int> sons;

	while (num != father[num]) {
		sons.push_back(num);
		num = father[num];
	}
	
	for (int son : sons) {
		father[son] = num;
	}

	return num;
}

void UnionFind::merge (int one, int two) {
	one = find (one);
	two = find (two);

	if (one == two) {
		return;
	}

	if (size[one] > size[two]) {
		father[two] = one;
		size[one] += size[two];
	}
	else {
		father[one] = two;
		size[two] += size[one];
	}

	count--;
}

int n;
int m;
vector<tuple<int, int, int>> roads;
vector<pair<int, int>> tree[N];
vector<tuple<int, int, int>> unpick;
int up[N][LOG];
int max1[N][LOG];
int max2[N][LOG];
int dep[N];

void dfs (int now, int dad, int num) {
	dep[now] = dep[dad] + 1;
	up[now][0] = dad;
	max1[now][0] = num;
	for (int i = 1; i < LOG; i++) {
		up[now][i] = up[up[now][i - 1]][i - 1];
		max1[now][i] = max (max1[up[now][i - 1]][i - 1], max1[now][i - 1]);

		if (max1[up[now][i - 1]][i - 1] != max1[now][i - 1]) {
			max2[now][i] = min (max1[up[now][i - 1]][i - 1], max1[now][i - 1]);
		}
		max2[now][i] = max (max2[now][i], max2[up[now][i - 1]][i - 1]);
		max2[now][i] = max (max2[now][i], max2[now][i - 1]);
	}
	for (auto [son, newnum] : tree[now]) {
		if (son == dad) {
			continue;
		}
		dfs (son, now, newnum);
	}
}

int lca (int u, int v) {
	if (dep[u] < dep[v]) {
		swap (u, v);
	}

	for (int i = LOG - 1; i >= 0; i--) {
		if (dep[up[u][i]] >= dep[v]) {
			u = up[u][i];
		}
	}

	if (u == v) {
		return u;
	}

	for (int i = LOG - 1; i >= 0; i--) {
		if (up[u][i] != up[v][i]) {
			u = up[u][i];
			v = up[v][i];
		}
	}

	return up[u][0];
}

int query (int u, int p, int w) {
	int res = 0;
	for (int i = LOG - 1; i >= 0; i--) {
		if (dep[up[u][i]] >= dep[p]) {
			if (max1[u][i] != w) {
				res = max (res, max1[u][i]);
			}
			else {
				res = max (res, max2[u][i]);
			}
			u = up[u][i];
		}
	}
	return res;
}

int main () {

	freopen ("secmst.in", "r", stdin);
	freopen ("secmst.out", "w", stdout);

	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		roads.emplace_back(w, u, v);
	}

	long long cc = 0;
	UnionFind uf(n + 1);
	sort (roads.begin(), roads.end());
	int i = 0;
	for (auto [w, u, v] : roads) {
		if (!uf.same(u, v)) {
			uf.merge(u, v);
			tree[u].emplace_back(v, w);
			tree[v].emplace_back(u, w);
			cc += w;
		}
		else {
			unpick.emplace_back(u, v, w);
		}
	}

	dfs (1, 0, 0);

	long long res = 0;
	for (auto [u, v, w] : unpick) {
		int p = lca (u, v);
		int res1 = query (u, p, w);
		int res2 = query (v, p, w);
		if (!res || res > cc - max (res1, res2) + w) {
			res = cc - max (res1, res2) + w;
		}
	}

	cout << res << endl;
	
	return 0;
}