1 /**************************************************************
  2     Problem: 3669
  3     User: Tunix
  4     Language: C++
  5     Result: Accepted
  6     Time:4752 ms
  7     Memory:7896 kb
  8 ****************************************************************/
  9  
 10 //BZOJ 3669
 11 #include<vector>
 12 #include<cstdio>
 13 #include<cstring>
 14 #include<cstdlib>
 15 #include<iostream>
 16 #include<algorithm>
 17 #define rep(i,n) for(int i=0;i<n;++i)
 18 #define F(i,j,n) for(int i=j;i<=n;++i)
 19 #define D(i,j,n) for(int i=j;i>=n;--i)
 20 using namespace std;
 21 int getint(){
 22     int v=0,sign=1; char ch=getchar();
 23     while(ch<‘0‘||ch>‘9‘){ if (ch==‘-‘) sign=-1; ch=getchar();}
 24     while(ch>=‘0‘&&ch<=‘9‘){ v=v*10+ch-‘0‘; ch=getchar();}
 25     return v*=sign;
 26 }
 27 const int N=150010,INF=~0u>>2;
 28 /******************tamplate*********************/
 29 struct LCT{
 30     int c[N][2],fa[N],v[N],mx[N];
 31     bool rev[N];
 32     int st[N],top;
 33 #define L c[x][0]
 34 #define R c[x][1]
 35     void Push_up(int x){
 36         mx[x]=x;
 37         if (v[mx[L]]>v[mx[x]]) mx[x]=mx[L];
 38         if (v[mx[R]]>v[mx[x]]) mx[x]=mx[R];
 39     }
 40     void Push_down(int x){
 41         if (rev[x]) rev[x]=0,rev[L]^=1,rev[R]^=1,swap(L,R);
 42     }
 43     bool not_root(int x){
 44         return c[fa[x]][0]==x || c[fa[x]][1]==x;
 45     }
 46     void rotate(int x){
 47         int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1;
 48         if (not_root(y)) c[z][c[z][1]==y]=x;
 49         fa[x]=z; fa[y]=x; fa[c[x][r]]=y;
 50         c[y][l]=c[x][r]; c[x][r]=y;
 51         Push_up(y);
 52     }
 53     void preview(int x){
 54         top=0; st[++top]=x;
 55         for(;not_root(x);x=fa[x])
 56             st[++top]=fa[x];
 57         D(i,top,1) Push_down(st[i]);
 58     }
 59     void splay(int x,int y=0){
 60         for(preview(x);not_root(x);rotate(x))
 61             if (not_root(y=fa[x]))
 62                 rotate( c[y][1]==x^c[fa[y]][1]==y ? x : y);
 63         Push_up(x);
 64     }
 65     void access(int x,int y=0){
 66         for(;x;splay(x),c[x][1]=y,y=x,x=fa[x]);
 67     }
 68     void makeroot(int x){
 69         access(x); splay(x); rev[x]^=1;
 70     }
 71     void link(int x,int y){
 72         makeroot(x);fa[x]=y;
 73     }
 74     void cut(int x,int y){
 75         makeroot(x);access(y);splay(y);
 76         if (c[y][0]==x) c[y][0]=fa[x]=0;
 77     }
 78     int query(int x,int y){
 79         makeroot(x),access(y),splay(y);
 80         return mx[y];
 81     }
 82 }t;
 83 /*********************LCT***********************/
 84 struct edge{
 85     int x,y,a,b;
 86     bool operator < (const edge &e) const {
 87         return a < e.a;
 88     }
 89 }e[N];
 90 int fa[N];
 91 int find(int x){return fa[x]==x ? x : fa[x]=find(fa[x]);}
 92  
 93 int main(){
 94 #ifndef ONLINE_JUDGE
 95     freopen("3669.in","r",stdin);
 96     freopen("3669.out","w",stdout);
 97 #endif
 98     int n,m;
 99     n=getint(); m=getint();
100     F(i,1,m){
101         e[i].x=getint(); e[i].y=getint();
102         e[i].a=getint(); e[i].b=getint();
103     }
104     sort(e+1,e+m+1);
105     F(i,1,m){
106         t.v[n+i]=e[i].b;
107         t.mx[n+i]=n+i;
108     }
109     F(i,1,n) fa[i]=i;
110      
111     int ans=INF;
112     F(i,1,m){
113         int f1=find(e[i].x),f2=find(e[i].y);
114         if (f1!=f2){
115             fa[f1]=f2;
116             t.link(e[i].x,n+i); t.link(e[i].y,n+i);
117         }
118         else{
119             int tmp=t.query(e[i].x,e[i].y);
120             if (e[i].b<t.v[tmp]){//这一步即可略去自环
121                 t.cut(e[tmp-n].x,tmp); t.cut(e[tmp-n].y,tmp);
122                 t.link(e[i].x,i+n); t.link(e[i].y,i+n);
123             }
124         }
125         f1=find(1); f2=find(n);
126         if (f1==f2)
127             ans=min(ans,e[i].a+t.v[t.query(1,n)]);
128     }
129     printf("%d\n",ans==INF ? -1 : ans);
130     return 0;
131 }