注意:本题数据卡边权
//注意:本题数据卡边权,所以既要维护最大边权,也要维护次大边权,最大边与次大边必须不相等
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=510,M=10010;
typedef long long ll;//数据比较大,生成树权值要用longlong存
int n,m;
struct Edge//维护a到b这条路径上最大边的权值
{
int a,b,w;
bool f;//判断是不是树边,true-树边,false-非树边
bool operator<(const Edge& t)const
{
return w<t.w;
}
}edge[M];
int par[N];//维护并查集父节点
int h[N],e[N*2],ne[N*2],w[N*2],idx;//维护最小生成树,无向图,有N*2条边
//注意:本题数据卡边权,所以既要维护最大边权,也要维护次大边权,最大边与次大边必须不相等
int dis1[N][N];//dis[a][b]维护a到b这条路径上最大边的权值
int dis2[N][N];//dis[a][b]维护a到b这条路径上次大边的权值
int find(int x)//查根
{
if(x!=par[x])par[x]=find(par[x]);
return par[x];
}
bool merge(int a,int b)//合并
{
a=find(a);
b=find(b);
if(a==b)return false;
par[a]=b;
return true;
}
void add(int a,int b,int c)//插入
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
// u代表到达的点,fa代表父节点,maxd1代表到达u点的路径中存在的最大边权,maxd2代表次大边权,d[]代表根节点的数组
void dfs(int u,int fa,int maxd1,int maxd2,int d1[],int d2[])
{
d1[u]=maxd1;//记录到达点u路径上的边权最大值
d2[u]=maxd2;//记录到达点u路径上的边权次大值
for(int i=h[u];~i;i=ne[i])//遍历点u的所有连接点
{
int j=e[i];
if(j!=fa)//不是父节点
{
//维护最大边权与次大边权
//深搜,max(maxd,w[i]),maxd代表到u的最大值,w代表到j的权值,两个取一个最大值
//dfs(j,u,max(maxd,w[i]),d);
int t=w[i];
if(t>maxd1)dfs(j,u,t,maxd1,d1,d2);//t大于最大边
else if(maxd1>t && t>maxd2)dfs(j,u,maxd1,t,d1,d2);//t大于次大边,并且完全小于最大边
else dfs(j,u,maxd1,maxd2,d1,d2);//t最小
}
}
}
int main()
{
cin>>n>>m;//输入
for(int i=0;i<m;i++)cin>>edge[i].a>>edge[i].b>>edge[i].w;
sort(edge,edge+m);//排序
memset(h,-1,sizeof h);//初始化邻接矩阵
for(int i=1;i<=n;i++)par[i]=i;//初始化并查集
ll sum=0;//记录最小生成树的权值
for(int i=0;i<m;i++)//kruskal
{
int a=edge[i].a,b=edge[i].b,w=edge[i].w;
if(merge(a,b))//合并成功
{
sum+=w;//累加最小生成树的权值
edge[i].f=true;//标记成树边
add(a,b,w),add(b,a,w);//加入最小生成树中
}
}
// cout<<sum<<endl;
//在最小生成树中,维护a到b这条路径上 最大边,次大边 的权值
for(int i=1;i<=n;i++)dfs(i,-1,0,0,dis1[i],dis2[i]);
ll res=1e18;//维护次小生成树
for(int i=0;i<m;i++)
if(!edge[i].f)//非树边
{
int a=edge[i].a,b=edge[i].b,w=edge[i].w;
/*
一般来说,在最小生成树中,不会存在w<dis[a][b]的情况,
否则将w这条边替换dis[a][b]中的边会出现更小的生成树
所以在最小生成树中,w>=dis[a][b]
本题求 严格的次小生成树,所以 w必须严格大于dis[a][b]
当不求严格的次小生成树的情况下,可以将 if(w>dis[a][b]) 省略掉
*/
if(w>dis1[a][b])//大于最大边权
res=min(res,sum+w-dis1[a][b]);
else if(w>dis2[a][b])//大于次大边权
res=min(res,sum+w-dis2[a][b]);
}
printf("%lld",res);//输出次小生成树
return 0;
}