记得去年模拟赛的时候好像YY出二分答案枚举a,b的暴力，过了55欸
然后看正解，为了将两维变成一维，将a排序，模拟Kruskal的加边过程，同时维护1到n的最大值，加入一条边e(u,v,a,b)时有以下两种情况：
1） 若u,v已连通，则找出u->v上最大的b'，若b<b'，则替换之，同时更新答案，注意e一定经过1->n，因为去掉b'所在边时1,n一定不连通，若加上e后1,n连通，则必经过e，由于a是有序的，所以a是路径上最大的a，用a+MAX_b[1->n]更新答案即可。
2）否则，直接加入边e;
显然以上操作可以用lct处理。
对于维护边的信息，考虑把边看成点，与原来的真正的节点一起构成一棵（或多棵）lct，将边的信息存在对应的点上，并保证真正的结点不会对答案产生影响（相当于只起连通的作用），对于这道题，保证w[x]=0(x是结点的结点),x(x是边的结点）即可。
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cstdio> using namespace std; // The default source begin-----------
const int MXD=~0u>>;
const int D=;
char in[D],out[*],*I=in,*O=out;
#define gc (*I++)
#define pc(x) ((*O++)=x)
#define tQ template <typename Q>
tQ void gt(Q&x) {
static char c,f;
for(f=;c=gc,!isdigit(c);)if(c=='-') f=;
for(x=;isdigit(c);c=gc) x=(x<<) + (x<<) +c-'';
f && (x=-x);
}
tQ void pt(Q x){
static char stk[];
static int top;
top=;
if(x==) pc('');
for(;x;x/=) stk[++top] = x%+'';
for(;top;top--) pc(stk[top]);
}
// The default source end----------- const int Maxn=,Maxm=;
int n,m;
struct Edge{
int u,v,a,b;
inline bool operator < (const Edge&rhs) const {
return a<rhs.a || (a==rhs.a && b<rhs.b);
}
inline void read() {
gt(u),gt(v),gt(a),gt(b);
}
}edges[Maxm]; int ch[Maxn+Maxm][],p[Maxn+Maxm],flip[Maxn+Maxm],mx[Maxn+Maxm],w[Maxn+Maxm]; #define l ch[x][0]
#define r ch[x][1]
void update(int x){
if(!x) return;
mx[x]=x;
if(w[mx[l]]>w[mx[x]]) mx[x]=mx[l];
if(w[mx[r]]>w[mx[x]]) mx[x]=mx[r];
}
void down(int x) {
if(!x || !flip[x]) return;
swap(l,r);
flip[l]^=;
flip[r]^=;
flip[x]=;
}
#undef l
#undef r
inline bool isroot(int x) {
return ch[p[x]][]!=x && ch[p[x]][]!=x;
}
inline void rotate(int x){
int y=p[x],z=p[y];
int l=ch[y][]==x,r=l^;
if(!isroot(y)){
ch[z][ch[z][]==y]=x;
}
p[y]=x;
p[ch[x][r]]=y;
p[x]=z; ch[y][l]=ch[x][r];
ch[x][r]=y; update(y);
// update(x);
} int stk[Maxn],top;
inline void splay(int x){
stk[top=]=x;
for(int t=x;!isroot(t);stk[++top]=t=p[t]);
for(;top;top--) down(stk[top]);
for(;!isroot(x);){
int y=p[x],z=p[y];
if(!isroot(y)) {
if( (ch[y][]==x) ^ (ch[z][]==y)) rotate(x);
else rotate(y);
}
rotate(x);
}
update(x);
} inline void access(int x) {
for(int t=;x;x=p[t=x]){
splay(x);
ch[x][]=t;
update(x);
}
} inline void newroot(int x) {
access(x);
splay(x);
flip[x]^=;
} inline void n_as(int u,int v){
newroot(u);
access(v);
splay(v);
} inline void Cut(int x,int y) {
n_as(x,y);
ch[y][]=p[x]=;
update(x);
} inline void Link(int x,int y) {
newroot(x);
p[x]=y;
} int fa[Maxn];
int Find(int x) {
return x==fa[x]?x:fa[x]=Find(fa[x]);
} inline bool Union(int x,int y){
x=Find(x);y=Find(y);
if(x==y) return ;
return fa[x]=y,;
} inline void ufs_init(int n) {
for(int i=;i<=n;i++) fa[i]=i;
} inline void init() {
gt(n),gt(m);
for(int i=;i<=m;i++) edges[i].read();
ufs_init(n);
} inline int getroot(int x) {
for(access(x),splay(x);ch[x][];x=ch[x][]);
return x;
} inline void work() {
sort(edges+,edges+m+);
int ans=MXD;
for(int i=;i<=m;i++) {
const Edge& e=edges[i];
w[i+n]=e.b;
if(Union(e.u,e.v)) {
Link(e.u,i+n);
Link(e.v,i+n);
}else {
n_as(e.u,e.v);
int t=mx[e.v];
if(w[t] > e.b) {
Cut(edges[t-n].u,t);
Cut(edges[t-n].v,t);
Link(e.u,i+n);
Link(e.v,i+n);
}
}
newroot();
if(getroot(n)==) {
access(n);
splay(n);
ans = min (ans,e.a + w[mx[n]]);
}
}
printf("%d\n",ans==MXD?-:ans);
} int main() {
#ifdef DEBUG
freopen("forest.in","r",stdin);
freopen("forest.out","w",stdout);
#endif
fread(in,,D,stdin);
init();
work(); return ;
}