记录编号	272600	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2014]魔法森林	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	2.263 s
提交时间	2016-06-17 16:41:29	内存使用	10.23 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 1e9;

int n, m;
int val[maxn << 1]; 

#define is_num(x) (x >= '0' and x <= '9')

inline int get_num() {
	int ans = 0;
	char tmp = getchar();
	while(!is_num(tmp)) tmp = getchar();
	while( is_num(tmp)) {
		ans = ans * 10 + tmp - '0';
		tmp = getchar();
	}
	return ans;
}

struct link_cut_tree {
private:
	struct node {
		int ls, rs, fa;
		int mxid;
		bool revc;
		node() { ls = rs = fa = revc = mxid = 0; }
	}ns[maxn << 2];
	
	inline void update(int tar) {
		if(!tar) return;
		int mxid = tar;
		int lsid = ns[ns[tar].ls].mxid, rsid = ns[ns[tar].rs].mxid;
		if(lsid and val[lsid] > val[mxid]) mxid = lsid;
		if(rsid and val[rsid] > val[mxid]) mxid = rsid;
		ns[tar].mxid = mxid;
	}
	
	inline bool is_root(int tar) {
		int fa = ns[tar].fa;
		return ns[fa].rs != tar and ns[fa].ls != tar;
	}
	
	inline void make_revc(int tar) {
		if(!tar) return;
		swap(ns[tar].ls, ns[tar].rs);
		
		ns[tar].revc ^= 1;
	}
	
	inline void push_down(int tar) {
		if(!tar) return;
		if(ns[tar].revc) {
			make_revc(ns[tar].ls);
			make_revc(ns[tar].rs);
			ns[tar].revc ^= 1;
		}
	}
	
	inline void zig(int &tar) {
		int fa = ns[tar].fa;
		if(ns[ns[fa].fa].ls == fa) ns[ns[fa].fa].ls = tar;
		if(ns[ns[fa].fa].rs == fa) ns[ns[fa].fa].rs = tar;
		ns[tar].fa = ns[fa].fa;
		ns[ns[tar].rs].fa = fa;
		ns[fa].ls = ns[tar].rs;
		ns[tar].rs = fa, ns[fa].fa = tar;
		update(fa);
	} 
	
	inline void zag(int &tar) {
		int fa = ns[tar].fa;
		if(ns[ns[fa].fa].ls == fa) ns[ns[fa].fa].ls = tar;
		if(ns[ns[fa].fa].rs == fa) ns[ns[fa].fa].rs = tar;
		ns[tar].fa = ns[fa].fa;
		ns[ns[tar].ls].fa = fa;
		ns[fa].rs = ns[tar].ls;
		ns[tar].ls = fa, ns[fa].fa = tar;
		update(fa);
	}
	
	inline void splay(int now) {
		int fa;
		push_down(now);
		while(!is_root(now)) {
			fa = ns[now].fa;
			push_down(ns[fa].fa), push_down(fa), push_down(now);
			if(is_root(fa)) {
				ns[fa].ls == now ? zig(now) : zag(now);
				break;
			}
			else {
				if(ns[ns[fa].fa].ls == fa) ns[fa].ls == now ? zig(fa) : zag(now), zig(now);
				else ns[fa].rs == now ? zag(fa) : zig(now), zag(now);
			}
		}
		update(now);
	}
	
	inline void access(int tar) {
		int la = 0;
		while(tar) {
			splay(tar);
			ns[tar].rs = la;
			update(tar);
			la = tar;
			tar = ns[tar].fa;
		}
	}

	inline void make_root(int tar) {
		access(tar);
		splay(tar);
		make_revc(tar);
	}
	
	inline int find_root(int tar) {
		access(tar);
		splay(tar);
		while(ns[tar].ls) {
			push_down(tar);
			tar = ns[tar].ls;
		}
		splay(tar);
		return tar;
	}
public:
	inline void link(int u, int v) {
		make_root(v);
		ns[v].fa = u;
	}
	
	inline void cut(int u, int v) {
		make_root(u); access(v); splay(u);
		ns[u].rs = 0, ns[v].fa = 0;
		update(u);
	}
	
	inline bool is_connect(int u, int v) {
		return find_root(u) == find_root(v);
	}
	
	inline int query_mx(int u, int v) {
		make_root(u); access(v); splay(v);
		return ns[v].mxid;
	}
}lct;

struct edge {
	int fr, to, va, vb;
	edge() {}
	edge(int fr_, int to_, int va_, int vb_) { fr = fr_, to = to_, va = va_, vb = vb_; }
	
	bool operator < (const edge &b) const {
		return va == b.va ? vb < b.vb : va < b.va;
	}
}e[maxn];

inline void read() {
	n = get_num();
	m = get_num();
	int fr, to, va, vb;
	for(int i = 1; i <= m; i++) {
		fr = get_num(); to = get_num();
		va = get_num(); vb = get_num();
		e[i] = edge(fr, to, va, vb);
	}
}

inline void add_edge(int i) {
	val[n + i] = e[i].vb;//只有访问i + n的时候才是有效访问 
	lct.link(n + i, e[i].to);
	lct.link(n + i, e[i].fr);
}

inline void solve() {
	sort(e + 1, e + m + 1);
	int ans = inf;
	
	for(int i = 1; i <= m; i++) {
		int fr = e[i].fr, to = e[i].to;
		if(lct.is_connect(fr, to)) {
			int tar = lct.query_mx(fr, to);
			if(val[tar] > e[i].vb) {
				lct.cut(tar, e[tar - n].fr);
				lct.cut(tar, e[tar - n].to);
				add_edge(i);
			}
		} else {
			add_edge(i);
		}
		
		if(lct.is_connect(1, n)) ans = min(ans, e[i].va + val[lct.query_mx(1, n)]);
	}
	
	printf("%d\n", ans == inf ? -1 : ans);
}

int main() {
	freopen("magicalforest.in",  "r", stdin);
	freopen("magicalforest.out", "w", stdout);
	read();
	solve();
	return 0;
}