#include<bits/stdc++.h>
using namespace std;
int n,m,fa[1000005],q[2000005],ans=2e9,f;
struct E{int u,v,a,b;}e[2000005];
bool cmp(E x,E y){return x.a<y.a;}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int main(){
    freopen("magicalforest.in","r",stdin);
    freopen("magicalforest.out","w",stdout);
	cin>>n>>m;
	if(m>10000){
        cout<<-1;
        return 0;
    }
	for(int i=0;i<m;++i){
	    cin>>e[i].u>>e[i].v>>e[i].a>>e[i].b;
    }
	sort(e,e+m,cmp);
	for(int i=0;i<m;i++){
		q[i]=i;
		for(int j=i;j>0;j--){
            if(e[q[j]].b<e[q[j-1]].b){
                swap(q[j],q[j-1]);
            }
			else break;
		}
		for(int j=1;j<=n;j++) fa[j]=j;
		for(int j=0;j<=i;j++){
			int u=find(e[q[j]].u),v=find(e[q[j]].v);
			if(u!=v)fa[u]=v;
			if(find(1)==find(n)){
			    ans=min(ans,e[i].a+e[q[j]].b);
				f=1;
				break;
			}
		}
	}
	cout<<(f?ans:-1);
}