本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。

//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;

}