记录编号	401902	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2014]魔法森林	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	2.110 s
提交时间	2017-05-04 14:44:59	内存使用	37.48 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e6+10;
struct edge{int f,t,a,b;}w[N];
bool cmp(const edge &x,const edge &y){
	return x.a<y.a;
}
int n,m,fa[N],son[N][2],Maxp[N];
bool rev[N],ise[N],root[N];
#define lc son[x][0]
#define rc son[x][1]
void flip(int x){
	rev[x]^=1;swap(lc,rc);
}
void update(int x){
	if (ise[x]) Maxp[x]=x-n;else Maxp[x]=0;
	if (lc&&w[Maxp[lc]].b>w[Maxp[x]].b) Maxp[x]=Maxp[lc];
	if (rc&&w[Maxp[rc]].b>w[Maxp[x]].b) Maxp[x]=Maxp[rc];
}
void pushdown(int x){
	if (x&&rev[x]) flip(lc),flip(rc),rev[x]=0;
}
void rot(int x){
	int y=fa[x],z=fa[y];
	bool b=(x==son[y][1]);
	fa[son[y][b]=son[x][!b]]=y;
	fa[son[x][!b]=y]=x;
	fa[x]=z;
	if (y==son[z][0]) son[z][0]=x;else
	if (y==son[z][1]) son[z][1]=x;
	root[x]=root[y];root[y]=0;
	update(y);update(x);
}
void splay(int x){
	pushdown(x);
	for (;!root[x];rot(x)){
		int y=fa[x],z=fa[y];
		pushdown(z);pushdown(y);pushdown(x);
		if (!root[y]&&!root[z]) rot((x==son[y][0])==(y==son[z][0])?y:x);
	}
}
void access(int x){
	splay(x);
	root[rc]=1;rc=0;
	update(x);
	while (fa[x]){
		int y=fa[x];
		splay(y);
		root[son[y][1]]=1;
		root[son[y][1]=x]=0;
		update(y);
		splay(x);
	}
}
void makeroot(int x){
	access(x);flip(x);
}
int S[N];
int find(int x){return x==S[x]?x:S[x]=find(S[x]);}
int main()
{
	freopen("magicalforest.in","r",stdin);
	freopen("magicalforest.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++)
		scanf("%d%d%d%d",&w[i].f,&w[i].t,&w[i].a,&w[i].b);
	sort(w+1,w+m+1,cmp);
	for (int i=1;i<=n+m;i++) S[i]=i,root[i]=1;
	for (int i=1;i<=m;i++) ise[i+n]=1,Maxp[i+n]=i;
	int ans=1e9;
	for (int i=1;i<=m;i++){
		int x=w[i].f,y=w[i].t;
		makeroot(x);
		if (find(x)!=find(y)) fa[fa[x]=i+n]=y;
		else{
			access(y);
			int id=Maxp[y];
			if (w[id].b>w[i].b){
				makeroot(w[id].f);
				int p=w[id].t;
				access(p);
				root[son[p][0]]=1;
				fa[son[p][0]]=0;
				son[p][0]=0;
				makeroot(x);
				fa[fa[x]=i+n]=y;
			}
		}
		S[find(x)]=find(y);
		if (find(1)==find(n)){
			makeroot(1);
			access(n);
			ans=min(ans,w[i].a+w[Maxp[n]].b);
		}
	}
	printf("%d\n",ans<1e9?ans:-1);
	return 0;
}