LCT裸题，不会的可以来这里看看。
步入正题，现将边按a排序，依次加入每一条边，同时维护路径上的最小生成树上的最大边权，如果两点不连通，就直接连通。
如果两点已经连通，就将该边与路径上较小的一条比较，选择小的那一条即可
统计答案时，如果1与n连通就求出路径上最大值与当前的a值相加，取最小的一个。
但边权不好处理，于是我们把X—>Y路径拆成X->Z->Y,将边权放在Z的点权上即可
下面是代码
#include<bits/stdc++.h>
using namespace std;
typedef int sign;
typedef long long ll;
#define For(i,a,b) for(register sign i=(sign)a;i<=(sign)b;++i)
#define Fordown(i,a,b) for(register sign i=(sign)a;i>=(sign)b;--i)
const int N=5e4+5,M=1e5+5;
bool cmax(sign &a,sign b){return (a<b)?a=b,1:0;}
bool cmin(sign &a,sign b){return (a>b)?a=b,1:0;}
template<typename T>T read()
{
T ans=0,f=1;
char ch=getchar();
while(!isdigit(ch)&&ch!='-')ch=getchar();
if(ch=='-')f=-1,ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch-'0'),ch=getchar();
return ans*f;
}
void file()
{
#ifndef ONLINE_JUDGE
freopen("LCT.in","r",stdin);
freopen("LCT.out","w",stdout);
#endif
}
int n,m;
int ch[N+M][2],fa[N+M],rev[N+M],edge[N+M],bl[N+M];
struct node
{
int u,v,a,b;
inline void init(){u=v=a=b=0;}
bool operator < (const node &x)const
{return a<x.a;}
}e[M];
inline void push_up(int x)
{
if(e[bl[x]].b>=e[edge[ch[x][0]]].b&&e[bl[x]].b>=e[edge[ch[x][1]]].b)edge[x]=bl[x];
else if(e[edge[ch[x][0]]].b>=e[edge[ch[x][1]]].b)edge[x]=edge[ch[x][0]];
else edge[x]=edge[ch[x][1]];
}
inline void push_down(int x)
{
if(rev[x])
{
rev[ch[x][0]]^=1;
rev[ch[x][1]]^=1;
swap(ch[x][0],ch[x][1]);
rev[x]=0;
}
}
inline bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
inline bool get(int x){return x==ch[fa[x]][1];}
inline void rotate(int x)
{
int old=fa[x],oldfa=fa[old],o=get(x);
if(!isroot(old))ch[oldfa][get(old)]=x;
fa[x]=oldfa;fa[ch[x][o^1]]=old;fa[old]=x;
ch[old][o]=ch[x][o^1];ch[x][o^1]=old;
push_up(old);push_up(x);
}
const int inf=0x3f3f3f3f;
int l[N+M],ans=inf;
inline void splay(int x)
{
l[0]=0;
int y=x;
while(1)
{
l[++l[0]]=y;
if(isroot(y))break;
y=fa[y];
}
Fordown(i,l[0],1)push_down(l[i]);
while(!isroot(x))
{
if(!isroot(fa[x]))rotate(get(x)^get(fa[x])?x:fa[x]);
rotate(x);
}
}
inline void access(int x)
{
for(register int y=0;x;y=x,x=fa[x])
{
splay(x);ch[x][1]=y;push_up(x);
}
}
inline void makeroot(int x)
{
access(x);splay(x);rev[x]^=1;
}
inline int find(int x)
{
access(x);splay(x);
while(ch[x][0])x=ch[x][0];
return x;
}
inline void cut(int x,int y)
{
makeroot(x);
access(y);splay(y);
if(ch[y][0]==x)ch[y][0]=fa[x]=0;
}
inline void link(int x,int y)
{
makeroot(x);fa[x]=y;
}
inline void deal(int i)
{
int x=e[i].u,y=e[i].v;
if(find(x)^find(y))link(x,i+n),link(i+n,y);
else
{
makeroot(x);
access(y);splay(y);
if(e[edge[y]].b>e[i].b)
{
int t=edge[y];
cut(t+n,e[t].u);
cut(t+n,e[t].v);
link(i+n,e[i].u);
link(i+n,e[i].v);
}
}
}
inline void input()
{
n=read<int>();m=read<int>();
For(i,1,m)
{
e[i].u=read<int>();
e[i].v=read<int>();
e[i].a=read<int>();
e[i].b=read<int>();
}
}
inline int cal()
{
if(find(1)^find(n))return inf;
makeroot(1);
access(n);splay(n);
return e[edge[n]].b;
}
inline void work()
{
sort(e+1,e+m+1);
e[0].init();
For(i,1,m)edge[i+n]=bl[i+n]=i;
For(i,1,m)
{
deal(i);
while(e[i].a==e[i+1].a)++i,deal(i);
cmin(ans,cal()+e[i].a);
}
printf("%d\n",ans==inf?-1:ans);
}
int main()
{
file();
input();
work();
return 0;
}