p4180kruskal+倍增lca80ptsWA#8#10求调（码风较为舒适）

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,ans,tot,lg,sec;

struct EDGE{
	int ver,nxt,w;
}edge[6 * 100005];
int head[100005];

struct node{
	int from,to,w;
}e[6 * 100005];

int d[100005],fa[100005][20],f[100005],maxn[100005][20],s[100005][20];

bool used[6 * 100005];

int read(){
	int x = 0,f = 1;
	char c = getchar();
	while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
	while(c >= '0' && c <= '9') x = x * 10 + c - '0',c = getchar();
	return x * f;
}

bool cmp(node x,node y){
	return x.w < y.w;
}

int get(int x){
	if(f[x] == x)
		return x;
	return f[x] = get(f[x]);
}

void add(int u,int v,int w){
	edge[++tot].ver = v;
	edge[tot].w = w;
	edge[tot].nxt = head[u];
	head[u] = tot;
}

void kruskal(){
	for(int i = 1;i <= n;i++)
		f[i] = i;
	for(int i = 1;i <= m;i++){
		int x = e[i].from;
		int y = e[i].to;
		int z = e[i].w;
		int r1 = get(x),r2 = get(y);
		if(r1 != r2){
			f[r1] = r2;
			ans += z;
			used[i] = true;
			add(x,y,z);
			add(y,x,z);
		}
	}
}

void dfs(int x,int dep){
	d[x] = dep;
	for(int i = head[x];i;i = edge[i].nxt){
		int y = edge[i].ver;
		int w = edge[i].w;
		if(!d[y]){
			fa[y][0] = x;
			maxn[y][0] = w;
			for(int j = 1;j <= lg;j++){
				fa[y][j] = fa[fa[x][j - 1]][j - 1];
				int big = max(maxn[y][j - 1],maxn[fa[y][j - 1]][j - 1]);
				int sma = min(maxn[y][j - 1],maxn[fa[y][j - 1]][j - 1]);
				if(big > maxn[y][j]){
					s[y][j] = maxn[y][j];
					maxn[y][j] = big;
				}
				if(sma < maxn[y][j] && sma > s[y][j])
					s[y][j] = sma;
			}
				
			dfs(y,dep + 1);
			
		}
	}
}

int lca(int x,int y,int z){
	int firs = 0,seco = 0;
	if(d[x] < d[y])
		swap(x,y);
	for(int i = lg;i >= 0;i--)
		if(d[fa[x][i]] >= d[y]){
			if(maxn[x][i] > firs){
				seco = firs,firs = maxn[x][i];
				if(s[x][i] > seco)
					seco = s[x][i];
			}
				
			else if(maxn[x][i] < firs && maxn[x][i] > seco){
				seco = maxn[x][i];
			}
				
			x = fa[x][i];
		}
	if(x == y){
		if(firs != z)
			return firs;
		return seco;
	}
		
	for(int i = lg;i >= 0;i--){
		if(fa[x][i] != fa[y][i]){
			if(maxn[x][i] > firs){
				seco = firs,firs = maxn[x][i];
				if(s[x][i] > seco)
					seco = s[x][i];
			}
				
			else if(maxn[x][i] < firs && maxn[x][i] > seco){
				seco = maxn[x][i];
			}
			
			if(maxn[y][i] > firs){
				seco = firs,firs = maxn[y][i];
				if(s[y][i] > seco)
					seco = s[y][i];
			}
				
			else if(maxn[y][i] < firs && maxn[y][i] > seco){
				seco = maxn[y][i];
			}
			
			x = fa[x][i],y = fa[y][i];
		}
	}
	if(maxn[x][0] > firs)
		seco = firs,firs = maxn[x][0];
	else if(maxn[x][0] > seco)
		seco = maxn[x][0];
	if(maxn[y][0] > firs)
		seco = firs,firs = maxn[y][0];
	else if(maxn[y][0] > seco)
		seco = maxn[y][0];
	if(firs < z)
		return firs;
	return seco;
}

signed main(){
	n = read(),m = read();
	lg = log(n) / log(2) + 1;
	for(int i = 1;i <= m;i++){
		e[i].from = read();
		e[i].to = read();
		e[i].w = read();
		
	}
	sec = 1e15;
	sort(e + 1,e + m + 1,cmp);
	
	kruskal();
	
	dfs(1,1);
	
	for(int i = 1;i <= m;i++){
		if(used[i])
			continue;
		int x = e[i].from,y = e[i].to,z = e[i].w;
		int change = lca(x,y,z);
		//printf("%d %d %d\n%d\n",x,y,z,change);
		if(change)
			sec = min(sec,ans + z - change);
	}
	printf("%d\n",sec);
	return 0;
}