记录编号	388984	评测结果	AAAAAAAAAA
题目名称	次小生成树	最终得分	100
用户昵称	rewine	是否通过	通过
代码语言	C++	运行时间	0.556 s
提交时间	2017-03-30 10:53:14	内存使用	165.87 MiB

#include <cstdio>
#include <queue>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL; 
inline void read(int &x) {
    static char c;bool flag = 0;
    while((c=getchar())<'0'||c>'9') flag |= (c=='-');
    x=c-'0';while((c=getchar())>='0'&&c<='9') x = x*10+c-'0';
    flag?x=-x:x;
}

#define N 310000

int n,m;
struct E {
	int to,w,next;
	E(int to=0,int w=0,int next=0):to(to),w(w),next(next){} 
}g[N*2];
int fr[N],tot;

void Add(int from,int to,int w) {
	g[++tot] = E(to,w,fr[from]);
	fr[from] = tot;
}

struct Da{int u,v,w,used;}a[N];
bool cmp(const Da &a,const Da &b) {return a.w<b.w;}
int f[N];
LL ans,det = ~0u>>2;

int find(int x) {
	return x==f[x]?x:f[x]=find(f[x]);
}

LL dep[N],fa[N][20+1],maxn[N][20+1],cmax[N][20+1];

void dfs(int t) {
	for (int i = fr[t]; i; i = g[i].next) {
		int to = g[i].to;
		if(to == fa[t][0]) continue;
		dep[to] = dep[t]+1;
		fa[to][0] = t; maxn[to][0] = g[i].w; 
		dfs(to);
	}
}

void init() {
	for (int j = 1; j < 20; j++)
	 for (int i = 1; i <= n; i++) {
	 	fa[i][j] = fa[fa[i][j-1]][j-1];
	 	if(fa[i][j]==0) continue;
	 	maxn[i][j] = max(maxn[i][j-1],maxn[fa[i][j-1]][j-1]);
	 	cmax[i][j] = max(cmax[i][j-1],cmax[fa[i][j-1]][j-1]);
	 	if(maxn[i][j-1] != maxn[fa[i][j-1]][j-1])
	 	  cmax[i][j] = max(cmax[i][j],min(maxn[i][j-1],maxn[fa[i][j-1]][j-1]));
	 }
}

LL ma,cm; 

void adjust(int &u,int deep) {
	for (int j = 20; j; j--)
	 if(dep[fa[u][j]] >= deep) {
	 	ma = max(ma,maxn[u][j]);
	    cm = max(cm,cmax[u][j]);
		u = fa[u][j];
	 }
}

void Try_add(int u,int v,int w) {
	ma = 0,cm = 0;
	if(dep[u] < dep[v]) swap(u,v);
	adjust(u,dep[v]);

    if(u != v) {
	  for (int j = 20; j; j--) 
	    if (fa[u][j] != fa[v][j]) {
	    	ma = max(ma,max(maxn[u][j],maxn[v][j]));
	        cm = max(cm,max(cmax[u][j],cmax[v][j]));
	     	u = fa[u][j]; v = fa[v][j]; 
	    }
	    ma = max(ma,max(maxn[u][0],maxn[v][0]));
	    cm = max(cm,max(cmax[u][0],cmax[v][0]));
	}
//cout<<" "" "<<w<<" "<<ma<<" "<<cm<<"\n";
	if(w > ma) det = min(det,w-ma);
	if(w > cm) det = min(det,w-cm);
}

int main() {
	freopen("secmst.in","r",stdin); freopen("secmst.out","w",stdout);
    read(n); read(m);
    for (int i = 1; i <= n; i++) f[i] = i; 
    for (int i = 1; i <= m; i++) 
    	read(a[i].u),read(a[i].v),read(a[i].w);
    sort(a+1,a+m+1,cmp);
	for (int i = 1; i <= m; i++) {
		int u = find(a[i].u),v = find(a[i].v);
		if(u != v) {
			f[u] = v; ans += a[i].w;
			a[i].used = 1;
			Add(u,v,a[i].w); Add(v,u,a[i].w);
		}
	}
	dep[1] = 1; dfs(1); init(); 
	for (int i = 1; i <= m; i++) 
	  if(!a[i].used) Try_add(a[i].u,a[i].v,a[i].w);
	printf("%lld\n",ans+det); 
    return 0;
}