RT

思路就是先最小生成树，然后倍增处理路径最大值与次大值

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
#define int long long
int read(){
	int x = 0;
	char ch = getchar();
	while(!isdigit(ch)) ch = getchar();
	while(isdigit(ch)){
		x = (x << 1) + (x << 3) + ch - '0';
		ch = getchar();
	}
	return x;
}

const int maxn = 1e5 + 7;
const int maxm = 3e5 + 7;
const ll inf = 99999999999999999999;
int n,m;
ll ans;

struct line{
	int u,v,w,nex;
    bool tag;
    void clear(){
    	u = v = w = nex = tag = 0;
	}
}e[maxm * 2];
int fir[maxn];

int tot;
void add(int a,int b,int c){
	e[++tot] = (line){a,b,c,fir[a]};
	fir[a] = tot;
}

void init(){
	n = read();
	m = read();
	for(int i = 1;i <= m; ++i){
		int a = read(),b = read(),c = read();
	    add(a,b,c);
	}
}

int bin[maxn];
bool cmp(line a,line b){
	return a.w < b.w;
}
int find(int x){
	if(bin[x] == x) return x;
	return bin[x] = find(bin[x]);
}

void kru(){
	for(int i = 1;i <= n; ++i) bin[i] = i;
	sort(e + 1,e + tot + 1,cmp);
	for(int i = 1;i <= m; ++i){
	//	cout<<e[i].w<<" ";
		int x = find(e[i].u),y = find(e[i].v);
		if(x != y) {
			bin[x] = y;
			e[i].tag = 1;
			ans += e[i].w;
		}
	}
	for(int i = 1;i <= m; ++i){
		if(e[i].tag) add(e[i].v,e[i].u,e[i].w),e[tot].tag = 1;
	}
}

int ee[4];
bool cmp1(int a,int b){
	return a > b;
}
int ask_min(int a,int b,int c,int d){
	ee[0] = a,ee[1] = b,ee[2] = c,ee[3] = d;
	sort(ee,ee + 4,cmp1);
	for(int i = 1;i < 4; ++i){
		if(ee[i] != ee[i - 1]) {
			return ee[i];
		}
	}
	return 0;
}

int dep[maxn],f[maxn][20];
int ma[maxn][20],mma[maxn][20];
void dfs(int x,int deep){
	dep[x] = deep;
	for(int i = 1;i < 20; ++i){
		f[x][i] = f[f[x][i - 1]][i - 1];
		ma[x][i] = max(ma[x][i - 1],ma[f[x][i - 1]][i - 1]);
		mma[x][i] = ask_min(ma[x][i - 1],mma[x][i - 1],ma[f[x][i - 1]][i - 1],mma[f[x][i - 1]][i - 1]);
	}
	for(int j = fir[x]; j ;j = e[j].nex){
		if(!e[j].tag) continue; 
		int to = e[j].v;
		if(dep[to]) continue;
		f[to][0] = x;
		ma[to][0] = e[j].w;
		mma[to][0] = 0;
		dfs(to,deep + 1);
	}
}

int up(int &x,int y){
	for(int i = 0;i < 20; ++i){
		if(y & (1 << i)) x = f[x][i];
	}
}
int lca(int x,int y){
	if(dep[x] < dep[y]) swap(x,y);
	up(x,dep[x] - dep[y]);
	if(x == y) return x;
	for(int i = 19;i >= 0; --i){
		if(f[x][i] != f[y][i]) x = f[x][i],y = f[y][i];
	}
	return f[x][0];
}

int ask(int x,int y,int z){
	int de = dep[x] - dep[y],res = 0;
	for(int i = 0;i < 20; ++i){
		if(de & (1 << i)){
			if(ma[x][i] == z) res = max(res,mma[x][i]);
			else res = max(res,ma[x][i]);
			x = f[x][i];
		}
	}
	return res;
}

ll work(){
	ll res = inf;
	for(int i = 1;i <= m; ++i){
		if(e[i].tag) continue;
		int x = e[i].u,y = e[i].v;
		if(x == y) continue;
		int z = lca(x,y);
		int num1 = ask(x,z,e[i].w),num2 = ask(y,z,e[i].w);
		num1 = max(num1,num2);
		if(num1 == 0) continue;
		res = min(res,(ll)e[i].w - num1);
	}
	return res;
}

signed main(){
	//freopen("12.in","r",stdin);
	init();
	kru();
	dfs(1,1);
	ans += work();
	printf("%lld\n",ans);
	return 0;
}