#include<bits/stdc++.h>
#define fa(p) tr[p].fa
#define lc(p) tr[p].ch[0]
#define rc(p) tr[p].ch[1]
#define nr(p) (lc(fa(p))==p||rc(fa(p))==p)
using namespace std;
typedef long long ll;
int n,m;
struct N{
	int v,mx,mi;
};
void get(int &a,int &b,int c,int d){
	if(c>a){
		a=c;
		b=d;
	}
}
struct LCT{
	int ch[2],fa,a,ma,ai,b,mb,bi,la;
}tr[1500010];
void pushup(int p){
	tr[p].ma=tr[p].a;tr[p].ai=p;
	get(tr[p].ma,tr[p].ai,tr[lc(p)].ma,tr[lc(p)].ai);
	get(tr[p].ma,tr[p].ai,tr[rc(p)].ma,tr[rc(p)].ai);
	tr[p].mb=tr[p].b;tr[p].bi=p;
	get(tr[p].mb,tr[p].bi,tr[lc(p)].mb,tr[lc(p)].bi);
	get(tr[p].mb,tr[p].bi,tr[rc(p)].mb,tr[rc(p)].bi);
} 
void pushdown(int p){
	if(tr[p].la){
		swap(lc(p),rc(p));
		tr[lc(p)].la^=1;
		tr[rc(p)].la^=1;
		tr[p].la=0;
	}
}
void rotate(int x){
	int y=fa(x),z=fa(y),k=rc(y)==x;
	if(nr(y))tr[z].ch[rc(z)==y]=x;fa(x)=z;
	tr[y].ch[k]=tr[x].ch[k^1];fa(tr[x].ch[k^1])=y;
	tr[x].ch[k^1]=y;fa(y)=x;
	pushup(y);pushup(x);
}
void pushall(int x){
	if(nr(x))pushall(fa(x));
	pushdown(x);
}
void splay(int x){
	pushall(x);
	while(nr(x)){
		int y=fa(x),z=fa(y);
		if(nr(y))((rc(y)==x)^(rc(z)==y))?rotate(x):rotate(y);
		rotate(x);
	}
}
void access(int x){
	for(int y=0;x;){
		splay(x);
		rc(x)=y;
		pushup(x);
		y=x;x=fa(x);
	}
}
void mkrt(int x){
	access(x);
	splay(x);
	tr[x].la^=1;
}
void split(int x,int y){
	mkrt(x);
	access(y);
	splay(y);
}
int fdrt(int x){
	access(x);
	splay(x);
	while(lc(x))pushdown(x),x=lc(x);
	splay(x);
	return x;
}
void link(int x,int y){
	mkrt(x);
	if(fdrt(y)!=x){
		fa(x)=y;
	}
}
void cut(int x,int y){
	mkrt(x);
	if(fdrt(y)==x&&fa(y)==x&&!lc(y)){
		fa(y)=0;
		pushup(x); 
	}
}
struct M{
	int x,y,a,b;
}E[1000010];
bool cmp(M a,M b){
	return a.a<b.a;
}
int fa[500010];
int find(int x){
	return fa[x]=(fa[x]==x?x:find(fa[x]));
} 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++){
		int x,y,a,b;
		cin>>x>>y>>a>>b;
		E[i]={x,y,a,b};
	}
	sort(E+1,E+1+m,cmp);
	for(int i=1;i<=m;i++){
		tr[i+n].a=E[i].a;
		tr[i+n].b=E[i].b; 
		pushup(i+n);
	}
	int ans=1e9;
	for(int i=1;i<=m;i++){
		int x=E[i].x,y=E[i].y,a=E[i].a,b=E[i].b;
		if(x==y)continue;
		int fx=find(x),fy=find(y);
		if(fx!=fy){
			fa[fx]=fy;
			link(x,n+i);
			link(y,n+i);
		} 
		else{
			split(x,y);
			if(tr[y].mb<=b)continue; 
			int id=tr[y].bi;
			if(id-n>0){
			cut(E[id-n].x,id);
			cut(E[id-n].y,id);
			link(x,i+n);
			link(y,i+n);
			}
		}
		if(find(1)==find(n)){
			split(1,n);
			ans=min(ans,tr[n].ma+tr[n].mb);
		}
	}
	cout<<(ans==1e9?-1:ans);
	return 0;
}

#include <bits/stdc++.h>
#define pa p[nd]
#define root nd[0].c[0]
#define maxV 50034
#define maxE 100034
using namespace std;

struct node{
    int v, rev, c[2], p;
}nd[maxV + maxE];

struct UFind{
    int sz, *p;
    UFind (): sz(0) {p = NULL;}
    ~UFind () {if(p) delete [] (p);}
    void resize(int size){
        if(p) delete [] (p); p = new int[(sz = size) + 1];
        for(int i = 0; i <= sz; i++) p[i] = i;
    }
    int ancestor(int x){return x == p[x] ? x : p[x] = ancestor(p[x]);}
    bool test(int x, int y, bool un = false){
        if((x = ancestor(x)) == (y = ancestor(y))) return true;
        if(un) p[x] = y; return false;
    }
};

struct edge{
    int u, v, a, b;
    edge (int u0 = 0, int v0 = 0, int a0 = 0, int b0 = 0): u(u0), v(v0), a(a0), b(b0) {}
    edge *scan(){scanf("%d%d%d%d", &u, &v, &a, &b); return this;}
    bool operator < (const edge &_) const {return a < _.a;}
};

int V, E, i, j;
int x, ans;
node g;
edge e[maxE];
UFind uf;

inline int dir(int x){return !x[nd].p ? -1 : x == x[nd].pa.c[0] ? 0 : x == x[nd].pa.c[1] ? 1 : -1;}

void reverse(int x){swap(x[nd].c[0], x[nd].c[1]); x[nd].rev ^= 1;}

void push_down(int x){if(x[nd].rev){reverse(x[nd].c[0]); reverse(x[nd].c[1]);} x[nd].rev = 0;}

void pull_down(int x){if(~dir(x)) pull_down(x[nd].p); push_down(x);}

void up(int &x, const int y){e[x].b < e[y].b ? x = y : 0;}

void update(int x){
    x[nd].v = max(x - V, 0);
    up(x[nd].v, x[nd].c[0][nd].v);
    up(x[nd].v, x[nd].c[1][nd].v);
}

void rotate(int x){
    int y = x[nd].p, d = !dir(x);
    nd[y[nd].c[!d] = x[nd].c[d]].p = y;
    x[nd].p = y[nd].p;
    if(~dir(y)) y[nd].pa.c[dir(y)] = x;
    nd[x[nd].c[d] = y].p = x;
    update(y); update(x);
}

void splay(int x){for(pull_down(x); ~dir(x); rotate(x))
    if(~dir(x[nd].p)) rotate(dir(x) ^ dir(x[nd].p) ? x : x[nd].p);}

void access(int x){for(int y = 0; x; y = x, x = x[nd].p){
    splay(x); x[nd].c[1] = y; update(x);}}

void make_root(int x){access(x); splay(x); reverse(x);}

int find_root(int x){access(x); splay(x); for(; x[nd].c[0]; x = x[nd].c[0]); return x;}

void link(int x, int y){make_root(x); x[nd].p = y;}

void split(int x, int y){make_root(x); access(y); splay(y);}

void cut(int x, int y){split(x, y); x[nd].p = y[nd].c[0] = 0; update(y);}

int query(int x, int y){split(x, y); return y;}

void cd(int h){
    if(uf.test(1, V)){
        node g = nd[query(1, V)];
        int res = e[g.v].b + e[h].a;
        (unsigned)res < (unsigned)ans ? ans = res : 0;
    }
}

int main(){
    scanf("%d%d", &V, &E);
    for(i = 1; i <= E; i++) e[i].scan();
    sort(e + 1, e + (E + 1));
    uf.resize(V);
    ans = -1;
    for(i = 1; i <= E; i++){
        edge &z = e[i];
        if(uf.test(z.u, z.v, true)){
            g = nd[query(z.u, z.v)];
            if(e[g.v].b > e[i].b){
                cut(e[g.v].u, g.v + V);
                cut(e[g.v].v, g.v + V);
            }else{
                cd(i);
                continue;
            }
        }
        nd[x = V + i].v = i;
        link(z.u, x);
        link(z.v, x);
        cd(i);
    }
    printf("%d\n", ans);
    return 0;
}