咕咕咕

直接扔代码好了

#include <bits/stdc++.h>
#define il inline
#define Max 1000005
#define ls(x) e[x].s[0]
#define rs(x) e[x].s[1]
#define fa(x) e[x].f
#define rv(x) e[x].rv
#define S(x) e[x].sm
using namespace std;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node
{
    int f,s[2],rv,sm;
}e[Max];
int n,m,st[Max],val[Max],tp,ans=0x3f3f3f3f;
il bool isroot(int x)
{
    return ls(fa(x))!=x&&rs(fa(x))!=x;
}
il void pushup(int x)
{
    S(x)=x;
    if(ls(x)&&val[S(ls(x))]>val[S(x)]) S(x)=S(ls(x));
    if(rs(x)&&val[S(rs(x))]>val[S(x)]) S(x)=S(rs(x));
}
il void pushdown(int x)
{
    if(rv(x))
    {
        rv(x)=0;
        swap(ls(x),rs(x));
        if(ls(x)) rv(ls(x))^=1;
        if(rs(x)) rv(rs(x))^=1;
    }
}
il int rlt(int x)
{
    return rs(fa(x))==x;
}
il void ct(int x,int f,int k)
{
    fa(x)=f;
    e[f].s[k]=x;
}
il void rot(int x)
{
    int y=fa(x),z=fa(y),ys=rlt(x),zs=rlt(y),k=e[x].s[ys^1];
    fa(x)=z;if(!isroot(y)) ct(x,z,zs);
    ct(k,y,ys),ct(y,x,ys^1);
    pushup(y),pushup(x);
}
il void splay(int x)
{
    tp=0;st[++tp]=x;
    int nw=x;
    while(!isroot(nw)) st[++tp]=nw=fa(nw);
    while(tp) pushdown(st[tp--]);
    for(int y=fa(x);!isroot(x);rot(x),y=fa(x))
    {
        if(!isroot(y))
            rot(rlt(x)==rlt(y)?x:y);
    }
}
il void access(int x)
{
    for(int y=0;x;x=fa(y=x))
        splay(x),rs(x)=y,pushup(x);
}
il void makeroot(int x)
{
    access(x);
    splay(x);
    rv(x)^=1;
    pushdown(x);
}
il int findroot(int x)
{
    access(x);splay(x);
    while(ls(x)) x=ls(x);
    return x;
}
il void split(int x,int y)
{
    makeroot(x);
    access(y);
    splay(y);
}
il void link(int x,int y)
{
    makeroot(x);
    if(findroot(y)!=x) fa(x)=y;
}
il void cut(int x,int y)
{
    split(x,y);
    if(ls(y)==x&&!rs(x)) ls(y)=fa(x)=0;
}
struct qry
{
    int a,b,x,y;
}q[Max];
int f[Max];
il int getf(int x)
{
    return (f[x]==x)?(x):(f[x]=getf(f[x]));
}
il void merge(int x,int y)
{
    int fx=getf(x),fy=getf(y);
    if(fx!=fy)
        f[fx]=fy;
}
il bool cmp(qry x,qry y)
{
    return x.b<y.b;
}
int main()
{
    n=read(),m=read();
    ans=0x3f3f3f3f;
    for(int i=1;i<=m;i++)
        q[i].x=read(),q[i].y=read(),q[i].a=read(),q[i].b=read();
    sort(q+1,q+1+m,cmp);
    for(int i=1;i<=n+m;i++) f[i]=S(i)=i;
    for(int i=n+1;i<=n+m;i++) val[i]=q[i-n].a;
    for(int i=1;i<=m;i++)
    {
        int u=q[i].x,v=q[i].y;
        bool flg=1;
        if(getf(u)==getf(v))
        {
            split(u,v);
            int w=S(v);
            if(val[w]>q[i].a)
                cut(q[w-n].x,w),cut(w,q[w-n].y);
            else flg=0;
        }
        else merge(u,v);
        if(flg) link(u,i+n),link(i+n,v);
        if(getf(1)==getf(n)) split(1,n),ans=min(ans,q[i].b+val[S(n)]);
    }
    if(ans<0x3f3f3f3f) cout<<ans<<endl;
    else puts("-1");
}