救救孩子吧。。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string.h>
using namespace std;
typedef long long ll;
int n,m;
struct node{
	ll u,v,w;
}edge[300005];
bool cmp(node & x,node & y)
{
	return x.w<y.w;
}
int lg[50];
ll pa[100005][50];
ll dep[100005];
ll vis[600005];
ll mst;
ll v[600005],ne[600005],w[600005],he[100005];
int cnt;
ll dis1[100005][50],dis2[100005][50];
ll inf=4e18,smst;
void add(int id,int to,int val)
{
	v[cnt]=to; w[cnt]=val;
	ne[cnt]=he[id]; he[id]=cnt++;
}
void init()
{
	mst=cnt=0;
	for(int i=1;i<=n;i++)
		for(int j=0;j<50;j++) pa[i][j]=0;
	for(int i=1;i<=n;i++) pa[i][0]=i;
	for(int i=0;i<100005;i++)
		for(int j=0;j<50;j++) dis1[i][j]=dis2[i][j]=-inf;
	memset(vis,0,sizeof vis);
	memset(he,-1,sizeof he);
	memset(dep,0,sizeof dep);
}
int find(int k)
{
	while(pa[k][0]!=k) k=pa[k][0];
	return k;
}
bool join(int x,int y)
{
	x=find(x),y=find(y);
	if(x==y) return 0;
	pa[x][0]=y;
	return 1;
}
void kru()
{
	int _cnt=0;
	for(int i=0;i<m;i++)
	{
		if(join(edge[i].u,edge[i].v))
		{
			_cnt++;
			mst+=edge[i].w;
			vis[i]=1;
			add(edge[i].u,edge[i].v,edge[i].w);
			add(edge[i].v,edge[i].u,edge[i].w);
		}
		if(_cnt==n-1) break;
	}
}
void upd(ll id,ll i,ll dis)
{
	if(dis>dis1[id][i]) dis2[id][i]=dis1[id][i],dis1[id][i]=dis;
	if(dis<dis1[id][i] && dis>dis2[id][i]) dis2[id][i]=dis;
}
void dfs(int id,int pre)
{
	pa[id][0]=pre; dep[id]=dep[pre]+1;
	
	for(int i=1;i<=lg[dep[id]];i++)
	{
		int pos=pa[id][i-1];
		pa[id][i]=pa[pos][i-1];
		upd(id,i,dis1[id][i-1]);//更新id->pos的最小值，次小值 
		upd(id,i,dis2[id][i-1]);
		upd(id,i,dis1[pos][i-1]);//更新pos->pa[id][i-1]的最小值，次小值 
		upd(id,i,dis2[pos][i-1]);
	}
	
	for(int i=he[id];~i;i=ne[i])
	{
		if(v[i]==pre) continue;
		dis1[v[i]][0]=w[i];
		dfs(v[i],id);
	}
}
ll d1,d2;//记录路径上的最小值，次小值 
void upd2(ll k)
{
	if(k>d1) d2=d1,d1=k;
	if(k<d1 && k>d2) d2=k;
}
void find_max(ll x,ll y)
{
	d1=d2=-inf;
	if(dep[x]<dep[y]) swap(x,y);
	
	while(dep[x]>dep[y])
	{
		upd2(dis1[x][lg[dep[x]-dep[y]]-1]);
		upd2(dis2[x][lg[dep[x]-dep[y]]-1]);
		x=pa[x][lg[dep[x]-dep[y]]-1];
	}
	if(x==y) return ;
	for(int k=lg[dep[x]];k>=0;k--)//一直循环到x，y父亲为公共祖先 
		if(pa[x][k]!=pa[y][k])
		{
			upd2(dis1[x][k]);
			upd2(dis2[x][k]);
			upd2(dis1[y][k]);
			upd2(dis2[y][k]);
			x=pa[x][k]; y=pa[y][k];
		}
	//更新最后一步的值 
	upd2(dis1[x][0]);
	upd2(dis2[x][0]);
	upd2(dis1[y][0]);
	upd2(dis2[y][0]);
}
void sol()
{
	int x,y;
	smst=4e18;
	for(int i=0;i<m;i++)
	{
		if(vis[i]) continue;
		find_max(edge[i].u,edge[i].v);
//		cout<<edge[i].u<<"->"<<edge[i].v<<" d1 d2 == "<<d1<<" "<<d2<<endl;
		if(edge[i].w>d1)
		{
			smst=min(smst,mst+edge[i].w-d1);
		}else if(edge[i].w>d2){
			smst=min(smst,mst+edge[i].w-d2);
		}
	}
}
int main()
{
	ll t,x,y,z;
	for(int i=1;i<50;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i);
//	cin>>t;
	t=1;
	while(t--)
	{
		scanf("%d %d",&n,&m);
		init();
		for(int i=0;i<m;i++)
		{
			scanf("%d %d %d",&edge[i].u,&edge[i].v,&edge[i].w);
		}
		sort(edge,edge+m,cmp);
		kru();
		dfs(1,0);
		sol();
		cout<<smst<<endl;
	}
	return 0;
}