0pts求条 本蒟蒻条了n个下午

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100007;
const int MAXM = 300007;
struct edge {
	int nxt, to, val;
} e[MAXN << 1];
int h[MAXN], cnt;
void add(int u, int v, int w) {
	e[++cnt].nxt = h[u];
	e[cnt].to = v;
	e[cnt].val = w;
	h[u] = cnt;
}
struct edge1 {
	int u, v, w;
	bool used;
} e1[MAXN];
bool cmp(edge1 a, edge1 b) {
	return a.w < b.w;
}
int n, m, fa[MAXN];
long long ans0;
int find(int x) {
	if (fa[x] != x) return fa[x] = find(fa[x]);
	return x;
}
void kruskal() {
	sort(e1 + 1, e1 + m + 1, cmp);
	for (int i = 1; i <= m; ++i) {
		int u = find(e1[i].u), v = find(e1[i].v);
		if (u == v) continue;
		ans0 += e1[i].w;
		add(e1[i].u, e1[i].v, e1[i].w);
		add(e1[i].v, e1[i].u, e1[i].w);
		e1[i].used = 1;
		fa[v] = u;
	}
}
int f[MAXN][20] = {0}, mx[MAXN][20] = {0}, mx2[MAXN][20] = {0}, dep[MAXN];
int dfs(int u) {
	dep[u] = dep[f[u][0]] + 1;
	for (int i = 1; i <= 18; ++i) {
		f[u][i] = f[f[u][i - 1]][i - 1];
		if (mx[u][i - 1] == mx[f[u][i - 1]][i - 1]) {
			mx[u][i] = mx[u][i - 1];
			mx2[u][i] = max(mx2[f[u][i - 1]][i - 1], mx2[u][i - 1]);
		}
		if (mx[u][i - 1] > mx[f[u][i - 1]][i - 1]) {
			mx[u][i] = mx[u][i - 1];
			mx2[u][i] = max(mx[f[u][i - 1]][i - 1], mx2[u][i - 1]);
		}
		if (mx[u][i - 1] < mx[f[u][i - 1]][i - 1]) {
			mx[u][i] = mx[f[u][i - 1]][i - 1];
			mx2[u][i] = max(mx[f[u][i - 1]][i - 1], mx2[u][i - 1]);
		}
	}
	for (int i = h[u]; i; i = e[i].nxt) {
		int v = e[i].to, w = e[i].val;
		if (v == f[u][0]) continue;
		f[v][0] = u;
		mx[v][0] = w;
		dfs(v);
	}
}
int lca(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	for (int i = 18; i >= 0; --i)
		if (dep[u] - dep[v] >= (1 << i))
			u = f[u][i];
	if (u == v) return u;
	for (int i = 8; i >= 0; --i)
		if (f[u][i] != f[v][i]) {
			u = f[u][i];
			v = f[v][i];
		}
	return f[u][0];
}
long long lca2(int u, int v, int w) {
	int l = lca(u, v);
	int nmx = 0, nmx2 = 0;
	for (int i = 18; i >= 0; --i) {
		if (dep[f[u][i]] >= dep[l]) {
			if (nmx == mx[u][i]) nmx2 = max(mx2[u][i], nmx2);
			if (nmx > mx[u][i]) nmx2 = max(mx[u][i], nmx2);
			if (nmx < mx[u][i]) {
				nmx2 = max(mx2[u][i], nmx);
				nmx = mx[u][i];
			}
			u = f[u][i];
		}
		if (dep[f[v][i]] >= dep[l]) {
			if (nmx == mx[v][i]) nmx2 = max(mx2[v][i], nmx2);
			if (nmx > mx[v][i]) nmx2 = max(mx[v][i], nmx2);
			if (nmx < mx[v][i]) {
				nmx2 = max(mx2[v][i], nmx);
				nmx = mx[v][i];
			}
			v = f[v][i];
		}
	}
	if (w != nmx) return ans0 - nmx + w;
	if (nmx2) return ans0 - nmx2 + w;
	return 0x7f7f7f7f7f7f7f7f;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		cnt++;
		scanf("%d%d%d", &e1[cnt].u, &e1[cnt].v, &e1[cnt].w);
		if (e1[i].v == e1[i].u) cnt--;
	}
	for (int i = 1; i <= n; ++i) fa[i] = i;
	kruskal();
	dfs(1);
	long long ans = 0x7f7f7f7f7f7f7f7f;
	for (int i = 1; i <= m; ++i)
		if (!e1[i].used)
			ans = min(ans, lca2(e1[i].u, e1[i].v, e1[i].w));
	printf("%d", ans);
	return 0;
}