题意：这是bc round 71 div 1 的 1004 直接去看中文题意
分析：
首先，一种合法方案对应了原图的一棵生成树。
我们知道，最小生成树有一个性质是最大边最小。
因此，我们可以枚举生成树的最小边，去掉比该边小的边后对新图求最小生成树，那么我们所要的最优解一定包含在其中。
时间复杂度O(Mlog M+M^2*a (N)，显然仅仅这个效率是不够的。
可以发现我们每次枚举后都重新求了最小生成树，事实上这是不必要的。
考虑从大到小枚举生成树的最小边，我们要做的实际上是每次加入一条边，维护当前图的最小生成树。
加入一条边时，我们需要判断这条边能否与之前的边构成环。
I 若能构成环，用该边替代环中最大边一定更优；
II 若不能构成环，直接加入该边即可。
找环中最大边可以用DFS 实现。若图中现有的边数为N-1N−1，我们就可以更新答案。
这样，事件复杂度就降到了O(M\log M+MN)O(MlogM+MN)。
更高的效率的方法，我们涉及的操作为加边、删边、查询路径最大边，因此可以使用LCT 来维护。
注：我按照题解写了一发，肯定是我手残，没有理解人家的意思，我发现我写出来还没题解上的效率不行的快
肯定我不行，
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=;
const int mod=1e9+;
const LL INF=INT_MAX;
int head[maxn],p;
struct Edge
{
LL u,v,next;
LL w,mark;
bool operator<(const Edge &e)const
{
return w<e.w;
}
} edge[],o[];
void add(int u,int v,int w)
{
edge[p].u=u;
edge[p].v=v;
edge[p].w=w;
edge[p].mark=;
edge[p].next=head[u];
head[u]=p++;
}
int fa[maxn];
int find(int x)
{
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
LL tmp,vv,_max;
void dfs(int u,int f,int res)
{
if(u==vv)
tmp=res;
for(int i=head[u]; ~i; i=edge[i].next)
{
if(edge[i].v==f)continue;
if(edge[i].mark)continue;
_max=max(_max,edge[i].w);
int c=res;
if(res==-||edge[i].w>edge[c].w)c=i;
dfs(edge[i].v,u,c);
}
}
int main()
{
int T,n,m;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=; i<=m; ++i)
scanf("%I64d%I64d%I64d",&o[i].u,&o[i].v,&o[i].w);
sort(o+,o++m);
for(int i=; i<=n; ++i)fa[i]=i;
p=;
memset(head,-,sizeof(head));
int cnt=;
LL ans=INF;
for(int i=m; i>; --i)
{
tmp=-,_max=,vv=o[i].v;
if(cnt==n-)
{
dfs(o[i].u,,-);
ans=min(ans,_max-o[i+].w);
}
int fx=find(o[i].u);
int fy=find(o[i].v);
if(fx!=fy)
{
++cnt;
fa[fx]=fy;
}
else
{
if(tmp==-)
dfs(o[i].u,,-);
edge[tmp].mark=edge[tmp^].mark=;
}
add(o[i].u,o[i].v,o[i].w);
add(o[i].v,o[i].u,o[i].w);
}
if(cnt==n-)
{
_max=;
dfs(,,-);
ans=min(ans,_max-o[].w);
}
if(ans==INF)printf("-1\n");
else printf("%I64d\n",ans);
}
return ;
}