当时在暑假早就讲了这道题了，只不过我现在才做了这道题。
题解：
我们要求次小生成树的话，考虑先把最小生成树求出来，因为如果我们用求最小生成树的话，边早已经从大到小排序好了，所以次小生成树的就是替换最小生成树上的一条边所得。
那么考虑如何来替换那一条边，要保证严格次小，那么我们需要替换掉最小生成树上两点间最大的边权，这样暴力枚举删边肯定是不行的，所以我们需要维护在最小生成树上的边。考虑用树链剖分来维护（其实就是打不来倍增）
然而维护的时候我们不仅要维护边权的最大值，还不能忘了再维护一个边权的次大值，因为最大值的边权有可能与我们枚举的非树边相等，不满足严格次小，所以还要维护次大值。
那么这道题的解法就很容易了，枚举非树边，然后用非树边替换求出次小生成树即可。时间复杂度nlogn+kruskal复杂度。
代码如下：
using namespace std;
const int maxn=1e6+7;
const long long inf=1e15;
struct node{
int x,y,val,flag;
}tree[maxn*4];
bool cmp(node a,node b){
return a.val<b.val;
}
struct dd{
int nxt,to,val;
}edge[maxn*3];
struct sb{
int l,r;
long long mx1,mx2;//维护最大值与次大值
}seg[maxn*4];
int n,m,x,y,v;
int fa[maxn];
int get(int x){
if(x==fa[x]) return x;
else return fa[x]=get(fa[x]);
}
int head[maxn],cnt;
void add(int x,int y,int v){
edge[++cnt].nxt=head[x];
edge[cnt].to=y;
edge[cnt].val=v;
head[x]=cnt;
}
long long ans;
void kruskal(){
ans=0;
int tot=0;
sort(tree+1,tree+1+m,cmp);
for(int i=1;i<=m;i++){
int f1=get(tree[i].x);
int f2=get(tree[i].y);
if(f1!=f2){
fa[f1]=f2;
ans+=tree[i].val;
tree[i].flag=1;
tot++;
if(tot==n-1) break;
}
}
for(int i=1;i<=m;i++){
if(tree[i].flag){
add(tree[i].x,tree[i].y,tree[i].val);
add(tree[i].y,tree[i].x,tree[i].val);
}
}
}
int w[maxn],dep[maxn],siz[maxn],faa[maxn],son[maxn];
void dfs1(int x,int f){
dep[x]=dep[f]+1;
faa[x]=f;
siz[x]=1;
int maxson=-1;
for(int i=head[x];i;i=edge[i].nxt){
int go=edge[i].to;
if(go==faa[x]) continue;
w[go]=edge[i].val;
dfs1(go,x);
siz[x]+=siz[go];
if(siz[go]>maxson){
maxson=siz[go];
son[x]=go;
}
}
}
int top[maxn],id[maxn],va[maxn],in;
void dfs2(int x,int topf){
top[x]=topf;
id[x]=++in;
va[id[x]]=w[x];
if(!son[x]) return;
dfs2(son[x],topf);
for(int i=head[x];i;i=edge[i].nxt){
int go=edge[i].to;
if(go==faa[x]||go==son[x]) continue;
dfs2(go,go);
}
}
void pushup(int now){
if(seg[now<<1].mx1>seg[now<<1|1].mx1){
seg[now].mx1=seg[now<<1].mx1;
seg[now].mx2=max(seg[now<<1].mx2,seg[now<<1|1].mx1);
}
if(seg[now<<1].mx1<seg[now<<1|1].mx1){
seg[now].mx1=seg[now<<1|1].mx1;
seg[now].mx2=max(seg[now<<1].mx1,seg[now<<1|1].mx2);
}
if(seg[now<<1].mx1==seg[now<<1|1].mx1){
seg[now].mx1=seg[now<<1].mx1;
seg[now].mx2=max(seg[now<<1].mx2,seg[now<<1|1].mx2);
}
}
void build(int now,int l,int r){
seg[now].l=l,seg[now].r=r;
if(l==r){
seg[now].mx1=va[l];
return;
}
int mid=(l+r)>>1;
build(now<<1,l,mid);
build(now<<1|1,mid+1,r);
pushup(now);
}
pair<int,int> getmax(pair<int,int> x,pair<int,int> y){
int ans1,ans2;
if(x.first>y.first){
ans1=x.first;
ans2=max(x.second,y.first);
}
if(x.first<y.first){
ans1=y.first;
ans2=max(x.first,y.second);
}
if(x.first==y.first){
ans1=x.first;
ans2=max(x.second,y.second);
}
return make_pair(ans1,ans2);
}
pair<int,int> query(int now,int l,int r){
if(seg[now].l>=l&&seg[now].r<=r) return make_pair(seg[now].mx1,seg[now].mx2);
int mid=(seg[now].l+seg[now].r)>>1;
pair<int,int> ans;
if(l<=mid) ans=getmax(ans,query(now<<1,l,r));
if(r>mid) ans=getmax(ans,query(now<<1|1,l,r));
return ans;
}
pair<int,int> link(int x,int y){
pair<int,int> res;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
res=getmax(res,query(1,id[top[x]],id[x]));
x=faa[top[x]];
}
if(dep[x]<dep[y]) swap(x,y);
res=getmax(res,query(1,id[y]+1,id[x]));
return res;
}
void solve(){
pair<int,int> ass;
long long save;
long long final=inf;
for(int i=1;i<=m;i++){
if(!tree[i].flag){
ass=link(tree[i].x,tree[i].y);
if(tree[i].val>ass.first){
save=ans;
final=min(final,save-ass.first+tree[i].val);
}
else if(tree[i].val>ass.second){
save=ans;
final=min(final,save-ass.second+tree[i].val);
}
}
}
printf("%lld\n",final);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++) scanf("%d%d%d",&tree[i].x,&tree[i].y,&tree[i].val);
kruskal();
dfs1(1,0);dfs2(1,1);build(1,1,n);
solve();
return 0;
}