记录编号	160925	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2014]魔法森林	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	3.160 s
提交时间	2015-04-29 21:47:02	内存使用	5.01 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int INF=0x7fffffff/2;
const int SIZET=150010,SIZEM=100010;
int value[SIZET];
class Node{
public:
	int fa;
	int lc,rc;
	int mxid;
	bool rev;
	#define fa(x) Tree[x].fa
	#define lc(x) Tree[x].lc
	#define rc(x) Tree[x].rc
	#define mxid(x) Tree[x].mxid
	#define rev(x) Tree[x].rev
}Tree[SIZET];
bool Is_Root(int x){
	return lc(fa(x))!=x&&rc(fa(x))!=x;
}
void Push_Down(int x){
	if(rev(x)){
		rev(x)=false;
		swap(lc(x),rc(x));
		if(lc(x)) rev(lc(x))^=1;
		if(rc(x)) rev(rc(x))^=1;
	}
}
void Update(int x){
	mxid(x)=x;
	if(value[mxid(lc(x))]>value[mxid(x)]){mxid(x)=mxid(lc(x));}
	if(value[mxid(rc(x))]>value[mxid(x)]){mxid(x)=mxid(rc(x));}
}
void Zig(int x){//右旋
	int y=fa(x),z=fa(y);
	if(lc(z)==y) lc(z)=x;
	if(rc(z)==y) rc(z)=x;
	fa(x)=z;
	lc(y)=rc(x);fa(lc(y))=y;
	rc(x)=y;fa(y)=x;
	Update(y);Update(x);
}
void Zag(int x){//左旋
	int y=fa(x),z=fa(y);
	if(lc(z)==y) lc(z)=x;
	if(rc(z)==y) rc(z)=x;
	fa(x)=z;
	rc(y)=lc(x);fa(rc(y))=y;
	lc(x)=y;fa(y)=x;
	Update(y);Update(x);
}
void Splay(int x){//把x整到当前伸展树的根
	Push_Down(x);
	while(!Is_Root(x)){
		int y=fa(x),z=fa(y);
		Push_Down(z);Push_Down(y);Push_Down(x);
		if(Is_Root(y)){
			if(lc(y)==x) Zig(x);
			else Zag(x);
			break;
		}
		else if(lc(y)==x){
			if(lc(z)==y) Zig(y),Zig(x);
			else Zig(x),Zag(x);
		}
		else{
			if(rc(z)==y) Zag(y),Zag(x);
			else Zag(x),Zig(x);
		}
	}
}
void Access(int x){//把x到根路径连成伸展树
	int y=0;
	while(x){
		Splay(x);
		rc(x)=y;
		Update(x);
		y=x;
		x=fa(x);
	}
}
int Get_Root(int x){
	Access(x);
	Splay(x);
	while(lc(x)){
		Push_Down(x);
		x=lc(x);
	}
	Splay(x);
	return x;
}
bool Is_Connected(int x,int y){
	return Get_Root(x)==Get_Root(y);
}
void Make_Root(int x){
	Access(x);
	Splay(x);
	rev(x)^=1;
}
void Link(int x,int y){
	Make_Root(x);
	fa(x)=y;
}
void Cut(int x,int y){
	Make_Root(x);
	Access(y);
	Splay(y);
	fa(lc(y))=0;lc(y)=0;
	Update(y);
}
int Path_Query(int x,int y){
	Make_Root(x);
	Access(y);
	Splay(y);
	return mxid(y);
}
class Edge{
public:
	int x,y,a,b;
};
bool operator < (const Edge &s,const Edge &t){
	if(s.a!=t.a) return s.a<t.a;
	return s.b<t.b;
}
int N,M;
Edge edges[SIZEM];
void Add_Edge(int k){
	Edge &e=edges[k];
	value[N+k]=e.b;
	Link(N+k,e.x);
	Link(N+k,e.y);
}
void Work(void){
	int ans=INF;
	for(int i=1;i<=M;i++){
		Edge &e=edges[i];
		if(!Is_Connected(e.x,e.y)) Add_Edge(i);
		else{
			int k=Path_Query(e.x,e.y);
			if(value[k]>e.b){
				Cut(k,edges[k-N].x);
				Cut(k,edges[k-N].y);
				Add_Edge(i);
			}
		}
		if(Is_Connected(1,N)){
			int k=Path_Query(1,N);
			ans=min(ans,e.a+value[k]);
		}
	}
	if(ans==INF) ans=-1;
	printf("%d\n",ans);
}
void Init(void){
	scanf("%d%d",&N,&M);
	for(int i=1;i<=M;i++)
		scanf("%d%d%d%d",&edges[i].x,&edges[i].y,&edges[i].a,&edges[i].b);
	sort(edges+1,edges+1+M);
}
int main(){
	freopen("magicalforest.in","r",stdin);
	freopen("magicalforest.out","w",stdout);
	Init();
	Work();
	return 0;
}