求边权最大值与最小值的差值最小的生成树，输出这个差值大小。

       按权值排序，我们等同于枚举最大值，然后更新生成树让生成树的最小值尽可能最大。

       也就是每次加入边，若构成环，则去掉环上最小值。

       若加入边不会构成环，则此时的差值 $gap$，一定是最优的 $gap$。

       若加入当前最大值的边会构成环，则去掉环上最小值后，更新当前的生成树中的值。重新计算 $gap$，只有 $gap$ 更小的时候，才更新 $bestgap$。

       几个小细节：

       1.由于我们要维护最小值，所以需要初始化为无穷大 $inf$。

       2.由于该题联通性不会变小（就是即使有 $cut$ 操作，也不会使得两个点失去联通性），所以可以使用并查集来判断是否成环，可以比 $LCT$ 的换根再判断是否根相同节约时间。

       3.倒过来的操作也是同理的，比如枚举最小值，更新最大值。

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define Ri register int
typedef long long LL;
const int maxn = 3e5 + 5;
const int inf = 1e9;struct node{int fa, son[2], val, res, id;   //  res is the xor resultbool tag;                   //  reverse lazy tag
}spl[maxn];#define ls(x) (spl[x].son[0])
#define rs(x) (spl[x].son[1])
#define fa(x) (spl[x].fa)
#define ident(x, fa) (rs(fa) == x)
#define connect(x, f, no) (spl[fa(x) = f].son[no] = x)
#define ntroot(x) (ls(fa(x)) == x || rs(fa(x)) == x)        // not the root of splay
#define reverse(x) swap(ls(x), rs(x)), spl[x].tag ^= true
inline void update(Ri x){Ri l = ls(x), r = rs(x);spl[x].res = spl[x].val;spl[x].id = x;if(spl[x].res > spl[l].res){spl[x].res = spl[l].res;spl[x].id = spl[l].id;}if(spl[x].res > spl[r].res){spl[x].res = spl[r].res;spl[x].id = spl[r].id;}
}inline void pushdown(Ri x){if(spl[x].tag){if(ls(x)) reverse(ls(x));if(rs(x)) reverse(rs(x));spl[x].tag = false;}
}inline void pushall(Ri x){if(ntroot(x)) pushall(fa(x));pushdown(x);
}inline void rotate(Ri x){Ri fa = fa(x), gf = fa(fa), k = ident(x, fa);connect(spl[x].son[k ^ 1], fa, k);fa(x) = gf;if(ntroot(fa)) spl[gf].son[ident(fa, gf)] = x;connect(fa, x, k ^ 1);update(fa), update(x);
}inline void splaying(Ri x){            // to the rootpushall(x);                         // push lazy tagwhile(ntroot(x)){int fa = fa(x), gf = fa(fa);if(ntroot(fa)) ident(fa, gf) ^ ident(x, fa) ? rotate(x) : rotate(fa);rotate(x);}
}inline void access(Ri x){              // link x to the rootfor(Ri y = 0; x; x = fa(y = x)){splaying(x);rs(x) = y;                      // link right son to the root of last splayupdate(x);}
}inline void mkroot(Ri x){              // trans the rootaccess(x);                          // link, and x will the right-most of the splay (the most dep)splaying(x);                        // after splaying, x will not have right sonreverse(x);                         // reverse the dep index
}inline int findroot(Ri x){             // find the root of splayaccess(x);splaying(x);while(ls(x)){pushdown(x);x = ls(x);}splaying(x);                        // prevent link too longreturn x;
}inline void link(Ri x, Ri y){mkroot(x);if(findroot(y) == x) return;        // x and y are in the same splay, not legalfa(x) = y;
}inline void cut(Ri x, Ri y){mkroot(x);if(findroot(y) != x || fa(y) != x || ls(y)) return; // not legalfa(y) = rs(x) = 0;update(x);
}inline void split(Ri x, Ri y){        // split the road x to ymkroot(x);access(y);splaying(y);// now y have no right son, and the left son is a road to the x// and the res of y is the res of the road x to y
}//---------------------------------
pair<int, int> his[maxn];
int edge, fa[maxn];
int gap, bestgap;
struct ooo{int u, v, c;inline bool operator <(const ooo&x) const &{return c < x.c;}
}all[maxn];multiset<int> minnum;inline int getroot(Ri x){return x == fa[x] ? x : fa[x] = getroot(fa[x]);
}inline void link1(const ooo &al){edge++;spl[edge].val = spl[edge].res = al.c;spl[edge].id = edge;his[edge].first = al.u;his[edge].second = al.v;link(al.u, edge);link(edge, al.v);minnum.insert(al.c);gap = *minnum.rbegin() - *minnum.begin();
}inline void link2(const ooo &al){split(al.u, al.v);Ri b = spl[al.v].id, c = spl[al.v].res;minnum.erase(minnum.find(c));cut(his[b].first, b);cut(b, his[b].second);link1(al);
}int main(){//IOS;Ri n, m, x, y;cin >> n >> m;edge = n;for(Ri i = 0; i <= n; i++){spl[i].res = spl[i].val = inf;fa[i] = i;}for(Ri i = 1; i <= m; i++)cin >> all[i].u >> all[i].v >> all[i].c;sort(all + 1, all + 1 + m);for(Ri i = 1; i <= m; i++){if(getroot(x = all[i].u) == getroot(y = all[i].v)){if(x == y) continue;link2(all[i]);if(gap < bestgap)bestgap = gap;}else{fa[fa[x]] = fa[y];link1(all[i]);bestgap = gap;}}cout << bestgap << endl;
}