首先将边排序，依次尝试加边。两个点不连通就连，否则把这条边取代两点之间权值最小的边。可以用$LCT$拆边为点维护。
考虑这种做法的正确性：
从小到大排序可以理解为枚举答案生成树的最大值（比它大的都在后面还没有加）。同时最小值也要尽量大，因此用较大的边替换较小的边一定更优。同时之前枚举的边也是用较大的边替换较小的边，也就最大化了最小值。
这样只要当前已经构成了生成树，就可以开始更新答案了。最大边就是当前枚举的边，最小边可以用平衡树维护。（一开始用的$multiset$，啥都没想直接$erase$，没想到会把所有的元素都清除掉，调了半小时。。。后来还是写的$treap$）
细节上注意数据中有自环，要判断一下。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 300005
#define inf 0x3f3f3f3f
#define pn putchar('\n')
#define px(x) putchar(x)
#define ps putchar(' ')
#define pd puts("======================")
#define pj puts("++++++++++++++++++++++")
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
template<typename T>
inline T read(){
T x=0;
int y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
inline int ran(){
static int seed=45562;
return seed=(seed*48271LL%2147483647);
}//优化常数的随机数函数
int n,m;
struct edge{
int from,to,l;
}e[maxn];
struct Link_Cut_Tree{
int mi[maxn],dat[maxn],son[maxn][2],fa[maxn],rev[maxn],st[maxn];
//dat是这个点（边）的权值，mi是权值最小的点的序号
//边的序号+n为它拆成的点
#define son(x,y) son[x][y]
#define whson(x) (son[fa[x]][1]==x)
#define root(x) (son[fa[x]][0]!=x&&son[fa[x]][1]!=x)
inline int MIN(int x,int y){
return dat[x]<dat[y]?x:y;
}
inline void update(int node){
mi[node]=MIN(node,MIN(mi[son(node,0)],mi[son(node,1)]));
}
inline void addedge(int s,int f,int wh){
if(s)fa[s]=f;
son(f,wh)=s;
}
inline void reverdown(int node){
swap(son(node,0),son(node,1));
rev[node]^=1;
}
inline void pushdown(int node){
if(rev[node]){
if(son(node,0))reverdown(son(node,0));
if(son(node,1))reverdown(son(node,1));
rev[node]=0;
}
}
inline void zhuan(int x){
int f=fa[x],gf=fa[f],wh=whson(x);
fa[x]=gf;
if(!root(f))son(gf,whson(f))=x;
addedge(son(x,wh^1),f,wh);
addedge(f,x,wh^1);
update(f),update(x);
}
inline void splay(int x){
int top=1,y=x;
st[1]=x;
while(!root(y))st[++top]=y=fa[y];
while(top)pushdown(st[top--]);
while(!root(x)){
y=fa[x];
if(!root(y))
zhuan(whson(x)^whson(y)?x:y);
zhuan(x);
}
}
void access(int x){
for(int y=0;x;y=x,x=fa[x])
splay(x),son(x,1)=y,update(x);
}
void makeroot(int x){
access(x),splay(x),reverdown(x);
}
void link(int x,int y){
makeroot(x);
fa[x]=y;
}
void cut(int x,int y){
makeroot(x),access(y),splay(y);
son(y,0)=fa[x]=0;
update(y);
}
int findroot(int x){
access(x),splay(x);
while(son(x,0))pushdown(x),x=son(x,0);
return x;
}
int Get(int x,int y){
makeroot(x),access(y),splay(y);
return mi[y];
}
Link_Cut_Tree(){
memset(dat,0x3f,sizeof dat);
}
}lct;
struct Treap{
int dat[maxn],ls[maxn],rs[maxn],ra[maxn],root,cnt;
#define ls(x) ls[x]
#define rs(x) rs[x]
void right(int &node){
int rec=ls(node);
ls(node)=rs(rec);
rs(rec)=node;
node=rec;
}
void left(int &node){
int rec=rs(node);
rs(node)=ls(rec);
ls(rec)=node;
node=rec;
}
void insert(int &node,int d){
if(!node){
node=++cnt;
ra[node]=ran();
dat[node]=d;
return;
}
if(dat[node]<d){
insert(rs(node),d);
if(ra[rs(node)]>ra[node])left(node);
}
else {
insert(ls(node),d);
if(ra[ls(node)]>ra[node])right(node);
}
}
void del(int &node,int d){
if(dat[node]==d){
if(ls(node)&&rs(node)){
if(ra[ls(node)]>ra[rs(node)])right(node),del(rs(node),d);
else left(node),del(ls(node),d);
}
else node=ls(node)+rs(node);
return;
}
if(dat[node]<d)del(rs(node),d);
else del(ls(node),d);
}
int getmin(){
int node=root;
while(ls(node))node=ls(node);
return dat[node];
}
}tr;
inline bool cmp(edge x,edge y){
return x.l<y.l;
}
void solve(){
int ans=inf,cnt=1;
for(register int i=1;i<=n;++i)
lct.mi[i]=i;
for(register int i=n+1;i<=n+m;++i)
lct.dat[i]=e[i-n].l,lct.mi[i]=i;
//lct初始化
for(register int i=1;i<=m;++i){
int x=e[i].from,y=e[i].to;
if(x==y)continue;//自环判断
tr.insert(tr.root,e[i].l);
if(lct.findroot(x)==lct.findroot(y)){
int k=lct.Get(x,y);
lct.cut(x,k),lct.cut(y,k);
tr.del(tr.root,e[k-n].l);
}
else ++cnt;
lct.link(x,i+n),lct.link(i+n,y);
if(cnt==n)ans=min(ans,e[i].l-tr.getmin());
//已经构成树，统计答案
}
printf("%d\n",ans);
}
int main(){
n=read(),m=read();
for(register int i=1;i<=m;++i)
e[i].from=read(),e[i].to=read(),e[i].l=read();
sort(e+1,e+1+m,cmp);
solve();
}
