记录编号	146223	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2014]魔法森林	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	1.762 s
提交时间	2015-01-13 14:02:29	内存使用	5.19 MiB

/*====================Asm.Def========================*/
#include <iostream>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <assert.h>
using namespace std;
inline void getd(int &x){
	char c = getchar();bool minus = 0;
	while(!isdigit(c) && c != '-')c = getchar();
	if(c == '-')minus = 1, c = getchar();
	x = c - '0';
	while(isdigit(c = getchar()))x = x * 10 + c - '0';
	if(minus)x = -x;
}
/*======================================================*/
const int maxn = 50002, maxm = 100003, INF = 0x3f3f3f3f;

//namespace LCT{
	int N, M;
	struct Edge{
		int u, v, A, B;
		inline bool operator < (const Edge &b)const{return A < b.A;}
	}E[maxm];
	
	struct Node *Nil;
	struct Node{
		Node *son[2], *p, *MaxE;
		int val;
		bool Rev;
		#define Max(a, b) (a->val > b->val ? a : b)
		#define LR(o) (o == o->p->son[1])
		inline bool IsRoot(){
			return (p == Nil) || (this != p->son[0] && this != p->son[1]);
		}
		inline void init(int v = 0){
			p = son[0] = son[1] = Nil;
			MaxE = this;
			val = v;
		}
		inline void update(){MaxE = Max(this, Max(son[0]->MaxE, son[1]->MaxE));}
		void push(){
			if(!IsRoot())p->push();
			if(Rev){
				Rev = false;
				son[0]->Rev ^= 1;son[1]->Rev ^= 1;
				swap(son[0], son[1]);
			}
		}
		inline void rot(){
			/*static */bool lr, plr, isrtp;
			isrtp = p->IsRoot();
			lr = LR(this);plr = LR(p);
			Node *&t = son[lr ^ 1];t->p = p;p->son[lr] = t;
			t = p;p = t->p;t->p = this;
			if(!isrtp)p->son[plr] = this;
			t->update();
		}
		inline void splay(){
			push();
			while(!IsRoot()){
				if(!p->IsRoot()){
					if(LR(this) == LR(p))p->rot();
					else rot();
				}
				rot();
			}
			update();
		}
	}node[maxn + maxm], *iter;
	inline void Access(Node *o){
		/*static */Node *son, *cur;son = Nil, cur = o;
		do{
			cur->splay();
			cur->son[1] = son;
			cur->update();
			son = cur;cur = cur->p;
		}while(cur != Nil);
		o->splay();
	}
	inline void MakeRoot(Node *o){
		Access(o);if(o->son[0] != Nil)o->Rev = true;
	}
	inline void Query(int a, int b, Node *&e){//保证ab连通
		/*static */Node *u, *v;u = node + a, v = node + b;
		MakeRoot(u);Access(v);
		e = v->MaxE;
	}
	inline void Del(Node *e){//保证e在重路径上
		e->splay();
		e->son[0]->p = e->p;e->son[1]->p = Nil;
	}
	inline void Insert(Edge *e){
		/*static */Node *u, *v, *t;u = node + e->u, v = node + e->v;
		t = iter++;t->init(e->B);
		MakeRoot(u);Access(v);
		u->p = t;t->p = v;
		Access(u);
	}
	
	struct UFS{
		int pre[maxn];
		inline void init(){for(int i = 1;i <= N;++i)pre[i] = i;}
		inline int find(int x){return pre[x] == x ? x : pre[x] = find(pre[x]);}
		inline void Union(int a, int b){pre[find(a)] = find(b);}
	}ufs;
	
	inline void init(){
		int i, m;
		getd(N);getd(m);
		Nil = node;
		iter = node + N + 1;
		for(i = 0;i <= N;++i)node[i].init();
		while(m--){
			getd(E[M].u), getd(E[M].v), getd(E[M].A), getd(E[M].B);
			if(E[M].u != E[M].v)++M;
		}
		sort(E, E + M);
		ufs.init();
	}
	
	inline void work(){
		int Ans = INF, A;
		Node *tmp;
		Edge *it = E, *end = E + M;
		while(it < end){
			A = it->A;
			while(it < end && it->A == A){
				if(ufs.find(it->u) != ufs.find(it->v))
					Insert(it), ufs.Union(it->u, it->v);
				else{
					Query(it->u, it->v, tmp);
					if(tmp->val > it->B){
						Del(tmp);
						Insert(it);
					}
					else{++it;continue;}
				}
				if(ufs.find(1) == ufs.find(N)){
					Query(1, N, tmp);
					Ans = min(Ans, A + tmp->val);
				}
				++it;
			}
		}
		printf("%d\n", Ans == INF ? -1 : Ans);
	}
//}


int main(){
	#if defined DEBUG
	freopen("test", "r", stdin);
	//freopen("output.txt", "w", stdout);
	#else
	freopen("magicalforest.in", "r", stdin);
	freopen("magicalforest.out", "w", stdout);
	#endif
	//using namespace LCT;
	init();
	
	work();
	
	#if defined DEBUG
	cout << endl << (double)clock()/CLOCKS_PER_SEC << endl;
	#endif
	return 0;
}