BJWC历史上最毒瘤的题，不卡常、不卡空间，但是如果你想一遍AC，真TM难。您是巨佬除外。

这里总结一下我与一些人犯的经典错误，希望提交记录里面不要满满的$50,80,90$了。

Part 1 检查初始化

①倍增跳LCA如果你预处理出来了$log$数组，应该是

lg[i]=log2(i)+1

而不是

lg[i]=log2(i)

②所有读入的自环没有意义，直接忽略；

③您的倍增求LCA写对了吗？您的倍增递推(求出次小值，次打值与$2^k$级父亲的)写对了吗？

④求出几个数的严格次小值的函数，您严格了吗？

⑤您的$inf$是不是设得太小了？

⑥您开$long\ long$了吗？

⑦您的数组开大了吗？建议全部开到$3$倍左右，会$MLE$除外。

Part 2 一些特别的函数

①请注意: 我们每次查询的是一条路径，而不是一条没有弯曲的链，所以需要$LCA$+两次链上查询。换句话说，$query(u,v)$的$u,v$可能并没有祖先关系。

②很多函数都要初始化$inf$，您都干这件事情了吗？

③随便造几组数据，看看您查询一条路径上的次小值的函数到底对还是没对。

Part 3 主函数

①如果您$TLE$了，请问并查集路径压缩了吗？

②您有没有将一条树边标记起来，这样最后扫到的只是非树边？

Part 4 提供Hack数据

LOJ上有两个人分别提供了一组Hack数据，点这里。

另外，建议您多造一些有自环与重边的图，自己试试看。

并且，假设样例过了，那么请尝试将样例中的一些边给调转一个方向，看看答案是否有变化。

Part 5 自己的代码

//4KB of shit

#include <bits/stdc++.h>
#define int long long
#define inf 4000000000000000007
using namespace std;
const int maxl=300005,maxg=25,maxm=300005;

int n,m,cnt=0,ans=inf,tot=0,pos=0,x,y,z;
int head[maxl],maxv[maxl][maxg],cmax[maxl][maxg],father[maxl][maxg];
int fa[maxl],depth[maxl],lg[maxl];

struct node{int u,v,w,c;}a[maxm];
struct edge{int next,to,dis;}e[maxm<<1];
bool cmp(node xx,node yy){return xx.w<yy.w;}
void add_edge(int u,int v,int w)
{
	cnt++;
	e[cnt].to=v,e[cnt].dis=w,e[cnt].next=head[u];
	head[u]=cnt;
}

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

int LCA(int u,int v)
{
	if (depth[u]<depth[v])  swap(u,v);
	while (depth[u]>depth[v])  u=father[u][lg[depth[u]-depth[v]]-1];
	if (u==v)  return u;
	
	for (int k=lg[depth[u]];k>=0;k--)
	  if (father[u][k]!=father[v][k])
	    u=father[u][k],v=father[v][k];
	return father[u][0];
}

int strict_second(int p1,int p2,int p3,int p4)
{
	int tmp[10]={0};
	tmp[1]=p1,tmp[2]=p2,tmp[3]=p3,tmp[4]=p4;
	sort(tmp+1,tmp+5);
	
	int res=-inf;
	if (tmp[3]<tmp[4])  res=tmp[3];
	else if (tmp[2]<tmp[4])  res=tmp[2];
	else if (tmp[1]<tmp[4])  res=tmp[1];
	return res;
}

void dfs(int now,int fath)
{
	depth[now]=depth[fath]+1;
	father[now][0]=fath;
	for (int i=1;i<=lg[depth[now]];i++)  father[now][i]=father[father[now][i-1]][i-1];
	for (int i=1;i<=lg[depth[now]];i++)  maxv[now][i]=max(maxv[now][i-1],maxv[father[now][i-1]][i-1]);
	for (int i=1;i<=lg[depth[now]];i++)
	  cmax[now][i]=strict_second(maxv[now][i-1],maxv[father[now][i-1]][i-1],cmax[now][i-1],cmax[father[now][i-1]][i-1]);
	for (int i=head[now];i;i=e[i].next)
	{
		int y=e[i].to;
		if (y==fath)  continue;
		maxv[y][0]=e[i].dis;
		dfs(y,now);
	}
}

int get_maxv(int u,int v)
{
	if (depth[u]<depth[v])  swap(u,v);
	
	int p=depth[u]-depth[v],res=-inf;
	for (int i=lg[depth[u]];i>=0;i--)
	{
		if (p&(1<<i))
		  res=max(res,maxv[u][i]),u=father[u][i]; 
	}
	return res;
}

int get_cmax(int u,int v)
{
	if (depth[u]<depth[v])  swap(u,v);
	
	int p=depth[u]-depth[v],res1=-inf,res2=-inf;
	for (int i=20;i>=0;i--)
	{
		if (p&(1<<i))
		{
			res2=strict_second(res1,res2,maxv[u][i],cmax[u][i]);
			res1=max(res1,maxv[u][i]);
			u=father[u][i];
		}
	}
	return res2;
}

int query_max(int u,int v)
{
	int f=LCA(u,v);
	return max(get_maxv(u,f),get_maxv(f,v));
}

int query_cmax(int u,int v)
{
	int f=LCA(u,v);
	int p1=get_maxv(u,f),p2=get_maxv(f,v);
	int p3=get_cmax(u,f),p4=get_cmax(f,v);
	return strict_second(p1,p2,p3,p4);
}

signed main()
{
	cin>>n>>m;
	for (int i=1;i<=n;i++)  fa[i]=i;
	for (int i=1;i<=n;i++)  lg[i]=log2(i)+1;
	for (int i=1;i<=m;i++)
	{
		cin>>x>>y>>z;
		if (x!=y)  a[++pos].u=x,a[pos].v=y,a[pos].w=z;
	}
	m=pos;
	sort(a+1,a+m+1,cmp);
	
	for (int i=1;i<=m;i++)
	{
		int x=fin(a[i].u),y=fin(a[i].v);
		if (x==y)  continue;
		else
		{
			add_edge(a[i].u,a[i].v,a[i].w);
			add_edge(a[i].v,a[i].u,a[i].w);
			fa[x]=y;
			a[i].c=1;
			tot+=a[i].w;
		}
	}
	for (int i=1;i<=n;i++)
		for (int j=0;j<=lg[n];j++)
		  maxv[i][j]=cmax[i][j]=-inf;
	dfs(1,0);
	
	for (int i=1;i<=m;i++)
	{
		if (a[i].c)  continue;
		
		int x=a[i].u,y=a[i].v;
		int tmp_maxv=query_max(x,y);
		if (tmp_maxv<a[i].w)
		{
			ans=min(ans,tot-tmp_maxv+a[i].w);
			continue;
		}
		else
		{
			tmp_maxv=query_cmax(x,y);
			ans=min(ans,tot-tmp_maxv+a[i].w);
		}
	}
	cout<<ans<<endl;
	
	return 0;
}