秘密的牛奶运输

/*
    求次小生成树的思路
     先把最小生成树建出来,再对这个树进行dfs，得到任意两点之间所经过的边中权值最大的边的权值dis[][]。
   依次枚举每条非树边，得到点a,b,权值w,判断这条边的权值w，是否大于dis[a][b],如果大于就进行更新判断
*/


#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

const int N=510,M=1e4+10;

typedef long long ll;
int n,m;
int h[N],e[N*2],w[N*2],ne[N*2],idx;
int dis[N][N];

struct node{
    int a,b,w;
    bool fg;
    bool operator<(const node&W)const
    {
        return w<W.w;
    }
}edge[M];

int p[N];

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

int find(int x)
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}
void dfs(int u,int fa,int maxv,int d[])
{
    d[u]=maxv;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        dfs(j,u,max(w[i],maxv),d);
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        edge[i]={a,b,c};
    }
    
    sort(edge,edge+m);
    
    ll sum=0;
    memset(h,-1,sizeof h);
    
    for(int i=0;i<m;i++)
    {
        int a=edge[i].a,b=edge[i].b,w=edge[i].w;
        a=find(a),b=find(b);
        if(a!=b)
        {
            p[a]=b;
            sum+=w;
            edge[i].fg=true;//标记这条边是树边
            add(a,b,w),add(b,a,w);//把最小生成树建出来
        }
    }
    
    for(int i=1;i<=n;i++) dfs(i,-1,0,dis[i]);//得到从i到其他任意点的的边权中的最大值
    
    ll res=1e18;
    
    for(int i=0;i<m;i++)
    {
        if(!edge[i].fg)
        {
            int a=edge[i].a,b=edge[i].b,w=edge[i].w;
            if(w>dis[a][b])
            res=min(res,sum-dis[a][b]+w);
        }
    }
    
    printf("%lld",res);
    
    return 0;
}