RE#10, loj上A了

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;
//#define int long long
const int N = 2e6;
const LL INF = 1e16;
struct node {
	int x, y; LL z;
} e[N];
int tot2, head2[N], nxt2[N], to2[N]; LL w2[N];
int ff[N], dep[N], fa[N];
LL f[N][30], g[N][30][3];
int n, m;
LL minn, max1, max2, val, ans = INF;

int cmp (node x, node y) {
	return x.z < y.z;
}

void add2 (int x, int y, LL z) {
	to2[++tot2] = y;
	w2[tot2] = z;
	nxt2[tot2] = head2[x];
	head2[x] = tot2;
}

int fd (int x) {
	if (x == fa[x]) return x;
	else return fa[x] = fd (fa[x]);
}

void kruskal () {
	sort (e + 1, e + 1 + m, cmp);
	for (int i = 1; i <= m; i ++) {
		int fx = fd (e[i].x), fy = fd (e[i].y);
		if (fx != fy) {
			fa[fx] = fy;
			add2 (e[i].x, e[i].y, e[i].z);
			add2 (e[i].y, e[i].x, e[i].z);
			ff[i] = 1;
			minn += e[i].z;
		}
	}
}

void dfs (int nd, int fa) {
	dep[nd] = dep[fa] + 1;
	for (int i = 0; i <= 19; i ++) {
		f[nd][i + 1] = f[f[nd][i]][i];
		g[nd][i + 1][0] = max (g[nd][i][0], g[f[nd][i]][i][0]);
		if (g[nd][i][0] == g[f[nd][i]][i][0]) g[nd][i + 1][1] = max (g[nd][i][1], g[f[nd][i]][i][1]);
		else if (g[nd][i][0] < g[f[nd][i]][i][0]) g[nd][i + 1][1] = max (g[nd][i][0], g[f[nd][i]][i][1]);
		else g[nd][i + 1][1] = max (g[f[nd][i]][i][0], g[nd][i][1]);
	}
	for (int i = head2[nd]; i; i = nxt2[i]) {
		int son = to2[i];
		if (son == fa) continue;
		f[son][0] = nd;
		g[son][0][0] = w2[i];
		g[son][0][1] = 0;
		dfs (son, nd);
	}
}

void lca (int x, int y) {
	vector <LL> a;
	a.clear();
	if (dep[x] < dep[y]) swap (x, y);
	for (int i = 20; i >= 0; i --) {
		if (dep[f[x][i]] >= dep[y]) {
			a.push_back (g[x][i][0]);
			a.push_back (g[x][i][1]);
			x = f[x][i];
		}
//		if (x == y) break;
	}
	if (x != y) {
		for (int i = 20; i >= 0; i -- ) {
			if (f[x][i] != f[y][i]) {
				a.push_back (g[x][i][0]);
				a.push_back (g[y][i][0]);
				a.push_back (g[x][i][1]);
				a.push_back (g[y][i][1]);
				x = f[x][i]; y = f[y][i];
			}
		}
		a.push_back (g[x][0][0]);
		a.push_back (g[y][0][0]);				
	}
	sort (a.begin(), a.end());
	int siz = unique (a.begin(), a.end()) - a.begin();
	if (siz >= 2) {
		max1 = a[siz - 1];
		max2 = a[siz - 2];
	}
	else {
		max1 = a[siz - 1];
		max2 = -INF;
	}
}

LL solve () {
	for (int i = 1; i <= m; i ++) {
		if (ff[i]) continue;
		lca (e[i].x, e[i].y);
		if (e[i].z == max1) ans = min (ans, minn - max2 + e[i].z);
		else ans = min (ans, minn - max1 + e[i].z);
	}
	return ans;
}

int main () {
	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++) fa[i] = i;
	for (int i = 1; i <= m; i ++) {
		scanf ("%d%d%lld", &e[i].x, &e[i].y, &e[i].z);
	}
	kruskal ();
	dep[1] = 1;
	dfs (1, 0);
	printf ("%lld\n", solve ());
//	return 0;
}