记录编号	444744	评测结果	AAAAAAAAAA
题目名称	次小生成树	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.420 s
提交时间	2017-09-04 08:22:05	内存使用	23.20 MiB

#include<bits/stdc++.h>//借鉴了哒哒哒大神的思路 
#define v e[i].to//倍增不好搞好像，树剖比较好 
#define mid (l+r)>>1
#define ls o<<1
#define rs o<<1|1
using namespace std;
const int inf=100005;
int ans,n,m,fi[inf],tot,fa[inf],dep[inf],size[inf],son[inf],top[inf],dfn[inf],pos[inf],tree_max[inf*4],tree_second[inf*4],f[inf],val[inf];
struct edge{
	int to,next,cost;
}e[600005];
struct hh{
	int to,from,cost,vis;
	bool operator <(const hh &b)const{
		return cost<b.cost;
	}
}E[600005];
void edge_add(int x,int y,int z){
	e[++tot].next=fi[x];
	e[tot].to=y;
	e[tot].cost=z;
	fi[x]=tot;
}
int get_f(int x){
	return x==f[x]?x:f[x]=get_f(f[x]);
}
void kruskal(){
	int k=n-1;
	sort(E+1,E+m+1);
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=m;i++){
		if(get_f(E[i].from)==get_f(E[i].to))continue;
		f[get_f(E[i].to)]=f[get_f(E[i].from)];
		ans+=E[i].cost;
		E[i].vis=1;
		edge_add(E[i].to,E[i].from,E[i].cost);
		edge_add(E[i].from,E[i].to,E[i].cost);
		k--;
		if(!k)break;
	}
}
void dfs1(int x){
	for(int i=fi[x];i;i=e[i].next){
		if(dep[v])continue;
		dep[v]=dep[x]+1;
		fa[v]=x;
		val[v]=e[i].cost;
		dfs1(v);
		size[x]+=size[v];
		if(size[v]>size[son[x]])son[x]=v;
	}
}
void dfs2(int x,int y){
	top[x]=y;
	dfn[x]=++tot;
	pos[tot]=x;
	if(son[x])dfs2(son[x],y);
	for(int i=fi[x];i;i=e[i].next){
		if(dfn[v])continue;
		dfs2(v,v);
	}
}
void build(int l,int r,int o){
	if(l==r){
		tree_max[o]=val[pos[l]];
		tree_second[o]=-0x3fffffff;
		return ;
	}
	build(l,mid,ls);
	build((mid)+1,r,rs);
	tree_max[o]=max(tree_max[ls],tree_max[rs]);
	if(tree_max[ls]>tree_max[rs])tree_second[o]=max(tree_max[rs],tree_second[ls]);
	if(tree_max[ls]<tree_max[rs])tree_second[o]=max(tree_max[ls],tree_second[rs]);
	if(tree_max[ls]==tree_max[rs])tree_second[o]=max(tree_second[rs],tree_second[ls]);
}
int q_max(int l,int r,int o,int L,int R,int p){
	if(l>=L&&r<=R){
		return tree_max[o]==p?tree_second[o]:tree_max[o];
	}
	int k=-0x3fffffff;
	if((mid)>=L)k=max(k,q_max(l,mid,ls,L,R,p));
	if((mid)<R)k=max(k,q_max((mid)+1,r,rs,L,R,p));
	return k;
}
int Q_max(int x,int y,int z){
	int ans=-0x3fffffff;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ans=max(ans,q_max(1,n,1,dfn[top[x]],dfn[x],z));
		x=fa[top[x]];
	}
	if(x!=y){
		if(dep[x]<dep[y])swap(x,y);
		ans=max(ans,q_max(1,n,1,dfn[y]+1,dfn[x],z));
	}
	return ans;
}
int main()
{
	freopen("secmst.in","r",stdin);
	freopen("secmst.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		E[i].from=x;
		E[i].to=y;
		E[i].cost=z;
	}
	for(int i=1;i<=n;i++)size[i]=1;
	kruskal();
	dep[1]=1;
	dfs1(1);
	tot=0;
	dfs2(1,1);
	build(1,n,1);
	int mi=0x3fffffff;
	for(int i=1;i<=m;i++){
		if(E[i].vis)continue;
		int num=Q_max(E[i].from,E[i].to,E[i].cost);
		mi=min(ans-num+E[i].cost,mi);
	}
	cout<<mi;
	return 0;
}