#include<bits/stdc++.h>
#define N 150000+5
#define INF 1234567890
using namespace std;
int n,m;
struct edge{
	int u,v,a,b;
}e[N];
bool cmp(edge x,edge y){
	return x.a<y.a;
}
int val[N],ch[N][2],fa[N],rev[N],mx[N],id[N];
void push_up(int x){
	mx[x]=val[x];id[x]=x;
	if(ch[x][0]&&mx[ch[x][0]]>mx[x]) mx[x]=mx[ch[x][0]],id[x]=id[ch[x][0]];
	if(ch[x][1]&&mx[ch[x][1]]>mx[x]) mx[x]=mx[ch[x][1]],id[x]=id[ch[x][1]]; 
}
void push_down(int x){
	if(rev[x]){
		rev[x]=0;
		swap(ch[x][0],ch[x][1]);
		rev[ch[x][0]]^=1;
		rev[ch[x][1]]^=1;
	}
}
bool get(int x){
	return x==ch[fa[x]][1];
}
bool isroot(int x){
	return x!=ch[fa[x]][0]&&x!=ch[fa[x]][1];
}
void rotate(int x){
	int y=fa[x],z=fa[y],chk=get(x);
	if(!isroot(y)) ch[z][y==ch[z][1]]=x;
	ch[y][chk]=ch[x][chk^1];
	fa[ch[x][chk^1]]=y;
	ch[x][chk^1]=y;
	fa[y]=x;
	fa[x]=z;
	push_up(y);
	push_up(x);
}
void update(int x){
	if(!isroot(x)) update(fa[x]);
	push_down(x);
}
void splay(int x){
	update(x);
	for(int f;f=fa[x],!isroot(x);rotate(x)){
		if(!isroot(f)) rotate(get(f)==get(x)?f:x);
	}
	push_up(x);
}
void access(int x){
	int p;
	for(p=0;x;p=x,x=fa[x]){
		splay(x);
		ch[x][1]=p;
		push_up(x);
	}
}
int findroot(int x){
	access(x);
	splay(x);
	while(ch[x][0]){
		push_down(x);
		x=ch[x][0];
	}
	splay(x);
	return x;
}
void makeroot(int x){
	access(x);
	splay(x);
	rev[x]^=1;
}
void split(int x,int y){
	makeroot(x);
	access(y);
	splay(y);
}
bool check(int x,int y){
	makeroot(x);
	if(findroot(y)==x) return true;
	return false; 
}
void link(int x,int y){
	makeroot(x);
	if(findroot(y)!=x) fa[x]=y;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].a,&e[i].b);
	for(int i=0;i<=n;i++) val[i]=-INF;
	sort(e+1,e+m+1,cmp);
	int ans=INF;
	for(int i=1;i<=m;i++){
		val[i+n]=e[i].b;
		int x=e[i].u,y=e[i].v;
		if(x==y){
			continue;
		}
		if(!check(x,y)){
			link(x,i+n);
			link(i+n,y);
		}
		else{
			split(x,y);
			int maxn=mx[y],idd=id[y];
			if(maxn<=val[i+n]) continue;
			splay(idd);
			fa[ch[idd][0]]=fa[ch[idd][1]]=0;
			link(x,i+n),link(i+n,y);
		}
		if(check(1,n)){
			split(1,n);
			ans=min(ans,mx[n]+e[i].a);
		}
	}
	if(ans==INF) cout<<-1<<endl;
	else printf("%d\n",ans);
	return 0;
}

只有10分，有MLE，也有RE。

求大佬查错