1 2 3 9 11wale 13re QAQ

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int ans=0;
int n,m;
struct Edge
{
	int x,y,z;
}te;
vector<Edge> edge;
vector<Edge> tree_edge;
vector<int> tree[110005];
bool used[110005];
int depth[110005];
int f[110005];
int fa[110005][25];
int maxn[110005][25];
int maxn2[110005][25];
bool cmp(Edge a,Edge b)
{
	return a.z<b.z;
}
int find(int a)
{
	if(f[a]==a)
	return a;
	f[a]=find(f[a]);
	return f[a];
}
void init()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		f[i]=i;
	}
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		te.x=x;
		te.y=y;
		te.z=z;
		if(x==y)
		continue;
		edge.push_back(te);
	}
}
void kruskal()
{
	sort(edge.begin(),edge.end(),cmp);
	for(int i=0;i<edge.size();i++)
	{
		int x,y,z;
		x=edge[i].x;
		y=edge[i].y;
		z=edge[i].z;
		if(find(x)!=find(y))
		{
			te.x=x;
			te.y=y;
			te.z=z;
			tree_edge.push_back(te);
			te.x=y;
			te.y=x;
			tree_edge.push_back(te);
			ans+=z;
			used[i]=1;
			f[find(y)]=find(x);
		}
	}
}
void dfs(int now,int father,int ev)
{
	fa[now][0]=father;
	maxn[now][0]=ev;
	maxn2[now][0]=0;
	depth[now]=depth[father]+1;
	for(int i=1;i<=20;i++)
	{
		fa[now][i]=fa[fa[now][i-1]][i-1];
	}
	for(int i=1;i<=20;i++)
	{
		maxn2[now][i]=max(maxn2[now][i-1],maxn2[fa[now][i-1]][i-1]);
		if(maxn[now][i-1]!=maxn[fa[now][i-1]][i-1])
		{
			maxn2[now][i]=max(maxn2[now][i],min(maxn[now][i-1],maxn[fa[now][i-1]][i-1]));
		}
		maxn[now][i]=max(maxn[now][i-1],maxn[fa[now][i-1]][i-1]);
	}
	for(int i=0;i<tree[now].size();i++)
	{
		int next=tree_edge[tree[now][i]].y;
		if(next==father)
		continue;
		int v=tree_edge[tree[now][i]].z;
		dfs(next,now,v);
	}
}
void build()
{
	for(int i=0;i<tree_edge.size();i++)
	{
		tree[tree_edge[i].x].push_back(i);
	} 
	dfs(1,0,0);
}
int LCA(int x,int y,int alternative)
{
	int maxa=0;
	int maxa2=0;
	if(depth[x]<depth[y])
	{
		swap(x,y);
	}
	for(int i=20;i>=0;i--)
	{
		if(depth[fa[x][i]]>=depth[y])
		{
			maxa2=max(maxn2[x][i],maxa2);
			if(maxa!=maxn[x][i])
			{
				maxa2=max(maxa2,min(maxa,maxn[x][i]));
			}
			maxa=max(maxa,maxn[x][i]);
			x=fa[x][i];
		}
	}
	if(x==y)
	return maxa2;
	for(int i=20;i>=0;i--)
	{
		if(fa[x][i]!=fa[y][i])
		{
			maxa2=max(maxn2[x][i],maxa2);
			if(maxa!=maxn[x][i])
			{
				maxa2=max(maxa2,min(maxa,maxn[x][i]));
			}
			maxa=max(maxa,maxn[y][i]);
			maxa2=max(maxn2[y][i],maxa2);
			if(maxa!=maxn[y][i])
			{
				maxa2=max(maxa2,min(maxa,maxn[y][i]));
			}
			maxa=max(maxa,maxn[y][i]);
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	if(maxa!=maxn[x][0])
	{
		maxa2=min(maxa,maxn[x][0]);
	}
	else
	{
		maxa2=max(maxn2[x][0],maxa2);
	}
	maxa=max(maxa,maxn[x][0]);
	if(maxa!=maxn[y][0])
	{
		maxa2=min(maxa,maxn[y][0]);
	}
	else
	{
		maxa2=max(maxn2[x][0],maxa2);
	}
	maxa=max(maxa,maxn[y][0]);
	if(alternative==maxa)
	{
		return maxa2;
	}
	return maxa;
}
int main()
{
	int minnn;
	init();
	kruskal();
	build();
	minnn=999999999;
	for(int i=0;i<edge.size();i++)
	{
		if(used[i]==0)
		{
			minnn=min(minnn,ans+edge[i].z-LCA(edge[i].x,edge[i].y,edge[i].z));//
		}
	}
	cout<<minnn;
	return 0;
}