鸽了很久的一道题（？）貌似是去年NOIP前听的emm...
首先我们分析一下最小生成树的性质
我们kruskal建树的时候呢是从小到大贪心加的边，这个的证明用到拟阵。（我太菜了不会）
首先我们不存在连接非树边比当前优的情况。
emm我们好像也就用这一条性质就够了。
步入正题
根据我们刚刚说的性质，我们可以枚举每一条边，使它和原来的树边形成一个环，然后我们需要求环上最大值，让我们的非树边替换掉这个边形成新的生成树。很显然这条边不会小于最大边，因为如果小于最大边的话，我们用这条边替换掉最大边会形成更小的生成树。如果这条边刚好等于最大边的话，那么我们求出来的不是严格次小生成树，而是非严格，因为两棵树的边权和相等。那么如果我们的非树边和最大值相等我们就不考虑了嘛（？）很显然不可以，因为我们可能有非树边-次大边更优的情况。所以我们维护链上最大值和次大值就可以啦。
Step1：建立最小生成树（这个很显然嘛，既然要求严格次小生成树，你肯定得先有棵树嘛）
Step2：处理生成树信息。
Step3：枚举每条非树边更新答案。
我来解释一下处理生成树信息都有啥。我们根据刚刚说的，我们需要维护链上最大值和次大值以及求LCA。这一步可以使用许多做法。我用的是倍增，然后树链剖分和LCT都是可以维护的。我才不想写LCT呢（傲娇脸）
容易错的地方的话我们一定要注意维护的次大值要严格小于最大值。
然后就到更新答案了。我们枚举的非树边有两种可能，横叉边or返祖边。分别讨论一下环的形态求链上比它严格小的最大值就可以了。
竟然1Abook思议
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 101000
#define maxm 301000
#define lgn 18
#define ll long long
#define inf 2002122520021225ll
using namespace std;
int f[maxn][lgn+2],mx[maxn][lgn+2],sc[maxn][lgn+2];
struct edge{int u,v,val;}e[maxm];
struct Edge{int to,lt,val;}E[maxn<<1];
int in[maxn],cnt,dep[maxn];bool used[maxm];
bool cmp(edge a,edge b){return a.val<b.val;}
int fa[maxn],n,m;ll sum,ans;bool vis[maxn];
void add(int x,int y,int v)
{
E[++cnt].lt=in[x];E[cnt].to=y;E[cnt].val=v;in[x]=cnt;
E[++cnt].lt=in[y];E[cnt].to=x;E[cnt].val=v;in[y]=cnt;
}
int find(int x)
{
int i=x,j;
while(fa[x]!=x) x=fa[x];
while(i!=x) j=fa[i],fa[i]=x,i=j;
return x;
}
void dfs(int x)
{
vis[x]=1;
for(int i=1;i<=lgn;i++)
{
f[x][i]=f[f[x][i-1]][i-1];
mx[x][i]=max(mx[x][i-1],mx[f[x][i-1]][i-1]);
sc[x][i]=max(sc[x][i-1],sc[f[x][i-1]][i-1]);
if(mx[x][i-1]>mx[f[x][i-1]][i-1])
sc[x][i]=max(sc[x][i],mx[f[x][i-1]][i-1]);
else if(mx[x][i-1]<mx[f[x][i-1]][i-1])
sc[x][i]=max(sc[x][i],mx[x][i-1]);
}
for(int i=in[x];i;i=E[i].lt)
{
int v=E[i].to;
if(vis[v]) continue;
f[v][0]=x;mx[v][0]=E[i].val;dep[v]=dep[x]+1;dfs(v);
}
}
int jump(int x,int len)
{
for(int i=lgn;~i;i--)
if(len&(1<<i))
x=f[x][i];
return x;
}
int LCA(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
x=jump(x,dep[x]-dep[y]);
if(x==y) return x;
for(int i=lgn;~i;i--)
if(f[x][i]^f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];
}
int getlink(int x,int len,int mm)
{
int qwq=0;
for(int i=lgn;~i;i--)
if(len&(1<<i))
{
if(mx[x][i]==mm) qwq=max(qwq,sc[x][i]);
else qwq=max(qwq,mx[x][i]);
x=f[x][i];
}
return qwq;
}
void kruskal()
{
int x,i,y,lca;
sort(e+1,e+m+1,cmp);
for(i=1;i<=n;i++) fa[i]=i;
for(i=1;i<=m;i++)
{
x=find(e[i].u),y=find(e[i].v);
if(x!=y)
{
fa[x]=y;ans+=(ll)e[i].val;
add(e[i].u,e[i].v,e[i].val);
used[i]=1;
}
}
dep[1]=1;dfs(1);sum=inf;
for(i=1;i<=m;i++)
{
if(!used[i])
{
x=e[i].u;y=e[i].v;
lca=LCA(x,y);
if(dep[x]<dep[y]) swap(x,y);
if(y==lca) sum=min(sum,ans-getlink(x,dep[x]-dep[lca],e[i].val)+e[i].val);
else sum=min(sum,ans-max(getlink(x,dep[x]-dep[lca],e[i].val),getlink(y,dep[y]-dep[lca],e[i].val))+e[i].val);
}
}
printf("%lld
",sum);
}
int main()
{
int i;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].val);
kruskal();
return 0;
}