```cpp
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<cstdlib>
#include<ctime>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define rev(i,a,b) for(register int i=a;i>=b;--i)
#define gra(i,u) for(register int i=head[u];i;i=edge[i].nxt)
#define Clear(a) memset(a,0,sizeof(a))
#define yes puts("YES")
#define no puts("NO")
using namespace std;
typedef long long ll;
const int INF(1e9+10);
const ll LLINF(1e18+10);
inline int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();
return s*w;
}
template<typename T>
inline T Min(T x,T y){return x<y?x:y;}
template<typename T>
inline T Max(T x,T y){return x>y?x:y;}
template<typename T>
inline void Swap(T&x,T&y){T t=x;x=y;y=t;return;}
template<typename T>
inline T Abs(T x){return x<0?-x:x;}
const int MAXN(6e5+10);
int n,m;
struct E{int u,v,w;};
E edge[MAXN];
struct Link_Cut_Tree
{
int fa[MAXN],ch[MAXN][2],pos[MAXN],maxx[MAXN],val[MAXN];
bool tag[MAXN];
inline void push_up(int u)
{
int ls=ch[u][0],rs=ch[u][1];
pos[u]=u;
if(maxx[ls]>maxx[rs]) pos[u]=pos[ls];
else pos[u]=pos[rs];
if(val[u]>=Max(maxx[ls],maxx[rs])) pos[u]=u;
maxx[u]=Max(Max(maxx[ls],maxx[rs]),val[u]);
return;
}
inline void lazy_tag(int u)
{
Swap(ch[u][0],ch[u][1]);
tag[u]^=1;
return;
}
inline void push_down(int u)
{
if(tag[u])
{
if(ch[u][0]) lazy_tag(ch[u][0]);
if(ch[u][1]) lazy_tag(ch[u][1]);
tag[u]=false;
}
return;
}
inline bool isroot(int u){return u!=ch[fa[u]][0]&&u!=ch[fa[u]][1];}
inline bool Get(int x){return x==ch[fa[x]][1];}
inline void update(int x)
{
if(!isroot(x)) update(fa[x]);
push_down(x);
return;
}
inline void rotate(int x)
{
int y=fa[x],z=fa[y],chk=Get(x);
if(!isroot(y)) ch[z][Get(y)]=x;
ch[y][chk]=ch[x][!chk],fa[ch[x][!chk]]=y;
ch[x][!chk]=y,fa[y]=x,fa[x]=z;
push_up(y);
push_up(x);
return;
}
inline void splay(int x)
{
update(x);
for(register int f=0;f=fa[x],!isroot(x);rotate(x))
if(!isroot(f)) rotate(Get(f)==Get(x)?f:x);
return;
}
inline void access(int x)
{
for(register int p=0;x;p=x,x=fa[x])
{
splay(x);
ch[x][1]=p;
push_up(x);
}
return;
}
inline void makeroot(int x)
{
access(x);
splay(x);
lazy_tag(x);
return;
}
inline int findroot(int x)
{
access(x);
splay(x);
push_down(x);
while(ch[x][0]) x=ch[x][0],push_down(x);
return x;
}
inline bool same(int x,int y){return findroot(x)==findroot(y);}
inline void link(int x,int y)
{
if(!same(x,y)) makeroot(x),fa[x]=y;
return;
}
inline void cut(int x,int y)
{
makeroot(x);
access(y);
splay(y);
if(ch[y][0]==x&&!ch[x][1]) ch[y][0]=fa[x]=0;
push_up(y);
return;
}
inline void split(int x,int y)
{
makeroot(x);
access(y);
splay(y);
return;
}
};
Link_Cut_Tree lct;
inline bool cmp(E x,E y){return x.w>y.w;}
int bian;
multiset<int>s;
inline void add(int p)
{
// puts("YES");
int u=edge[p].u,v=edge[p].v,w=edge[p].w;
if(u==v) return;
int newnode=p+n;
if(!lct.same(u,v))
{
lct.val[newnode]=w;
lct.link(u,newnode);
lct.link(newnode,v);
s.insert(w);
++bian;
return;
}
lct.split(u,v);
int pos=lct.pos[v]-n;
if(edge[pos].w>w)
{
lct.cut(edge[pos].u,pos+n);
lct.cut(pos+n,edge[pos].v);
s.erase(edge[pos].w);
lct.val[newnode]=w;
lct.link(u,newnode);
lct.link(newnode,v);
s.insert(edge[p].w);
}
return;
}
int main()
{
// freopen("read.txt","r",stdin);
n=read(),m=read();
rep(i,1,m) edge[i].u=read(),edge[i].v=read(),edge[i].w=read();
sort(edge+1,edge+1+m,cmp);
int p(1),ans(INF);
rev(i,edge[1].w,1)
{
while(edge[p].w>=i&&p<=m) add(p),++p;
if(bian==n-1)
{
set<int>::iterator it=s.end();
--it;
ans=Min(ans,*it-i);
}
}
printf("%d\n",ans);
return 0;
}
/*
Date : 2022/8/27
Author : UperFicial
Start coding at : 9:31
finish debugging at :
*/
```
by UperFicial @ 2022-08-27 11:30:05
调出来了。
用 $\texttt{multiset}$ 如果只删除一个元素 $x$，一定不要写 `s.erase(x)`，这样会删除所有与 $x$ 相等的元素，应该先 `s.find(x)` 找到 $x$ 的迭代器 $it$，然后 `s.erase(it)` 才能删除一个元素。
by UperFicial @ 2022-08-29 11:31:58
放在这里给大家提个醒/ll/ll/ll
by UperFicial @ 2022-08-29 11:32:17
太感谢了/bx
by Gao_yc @ 2022-09-08 21:55:24
@[UperFicial](/user/360511) 太感谢了（
by lzqy_ @ 2022-12-27 11:37:47
@[UperFicial](/user/360511) 太感谢了，前车之鉴
by Code_星云 @ 2022-12-27 21:57:38