本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
题目链接：BZOJ
正解：LCT
解题报告：
考虑这种两维约束的问题，一般都是限制一维，最小化另一维度。
那么我按a排序之后，一条一条往里面加，如果不连通，直接加进去，否则肯定是查询一下原来的边上的最大的b权值。
如果当前b权值大于最大的b值就不管，否则应该删掉这条最大的边，把这条新的边加进去。
显然加边删边用LCT就可以解决，而边权的查询如何维护呢？
如果是点权就很好办了，我们不妨把边权想点办法变成点权。
直接在这条边连接的两个点之间新建一个点，作为中转点，点权就是原边边权。这样我们就巧妙地把边权转换成好维护的点权了。
考虑这样做的正确性，因为辅助树实质上与原树并无关联，始终都能保持原树的相对位置。所以加入的这个虚点不会被剥离出来。
又因为一些SB的细节错误调了很久...
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <complex>
using namespace std;
typedef long long LL;
typedef long double LB;
typedef complex<double> C;
const double pi = acos(-1);
const int MAXN = 250011;
const int MAXM = 100011;
int n,m,tr[MAXN][2],tag[MAXN],father[MAXN],ans,pos,F[MAXN];
int top,stack[MAXN],a[MAXN],mx[MAXN],from[MAXN],match[MAXN][2];
struct edge{ int x,y,a,b; }e[MAXM];
inline bool cmpa(edge q,edge qq){ if(q.a==qq.a) return q.b<qq.b; return q.a<qq.a; }
inline bool isroot(int x){ return (tr[father[x]][0]!=x) && (tr[father[x]][1]!=x); }
inline void upd(int x,int y){ if(mx[y]>mx[x]) { mx[x]=mx[y]; from[x]=from[y]; } }
inline int find(int x){ if(F[x]!=x) F[x]=find(F[x]); return F[x]; }
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
}
inline void update(int x){
mx[x]=a[x]; from[x]=x;
int l=tr[x][0],r=tr[x][1];
if(l) upd(x,l);
if(r) upd(x,r);
}
inline void pushdown(int x){
if(tag[x]==0) return ;
tag[tr[x][0]]^=1; tag[tr[x][1]]^=1;
tag[x]=0;//!!!
swap(tr[x][0],tr[x][1]);
}
inline void rotate(int x){
int y,z; y=father[x]; z=father[y];
int l,r; l=(tr[y][1]==x); r=l^1;
if(!isroot(y)) tr[z][(tr[z][1]==y)]=x;
father[x]=z; father[y]=x;
father[tr[x][r]]=y; tr[y][l]=tr[x][r]; tr[x][r]=y;
update(y); update(x);
}
inline void splay(int x){
top=0; stack[++top]=x; int y,z;
for(int i=x;!isroot(i);i=father[i]) stack[++top]=father[i];
for(int i=top;i>=1;i--) pushdown(stack[i]);
while(!isroot(x)) {
y=father[x]; z=father[y];
if(!isroot(y)) {
if((tr[y][0]==x) ^ (tr[z][0]==y)) rotate(x);
else rotate(y);
}
rotate(x);
}
}
inline void access(int x){
int last=0;
while(x) {
splay(x);
tr[x][1]=last;
update(x);/*!!!*/
last=x;
x=father[x];
}
}
inline void move_to_root(int x){
access(x);
splay(x);
tag[x]^=1;
}
inline void link(int x,int y){
move_to_root(x);
father[x]=y;
//splay(x);
}
inline void cut(int x,int y){
move_to_root(x); access(y); splay(y);
tr[y][0]=father[x]=0; update(y);/*!!!*/
}
inline void build(edge b){
n++; a[n]=b.b; match[n][0]=b.x; match[n][1]=b.y;
link(b.x,n);
link(b.y,n);
}
inline int query(int x,int y){
move_to_root(x);
access(y);
splay(y);//!!!
pos=from[y];
return mx[y];
}
inline void work(){
n=getint(); m=getint(); for(int i=1;i<=m;i++) { e[i].x=getint(); e[i].y=getint(); e[i].a=getint(); e[i].b=getint(); }
sort(e+1,e+m+1,cmpa); int now; ans=(1<<30); int savn=n;
for(int i=n+m;i>=1;i--) F[i]=i;
for(int i=1;i<=m;i++) {
if(find(e[i].x)!=find(e[i].y)) {
build(e[i]);
F[find(e[i].x)]=find(e[i].y);
if(find(1)==find(savn))
ans=min(ans,query(1,savn)+e[i].a);
continue;
}
now=query(e[i].x,e[i].y);
if(now<=e[i].b) continue;
cut(pos,match[pos][0]);
cut(pos,match[pos][1]);
build(e[i]);
if(find(1)==find(savn))
ans=min(ans,e[i].a+query(1,savn));
}
if(ans==(1<<30)) printf("-1");
else printf("%d",ans);
}
int main()
{
work();
return 0;
}