#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
const int M=1e5+10;
const int INF=0x3f3f3f3f;
int n,m,s1=INF,s2=INF,mk[N];
bool flag=0;
struct node{
    int v,w1,w2;
};
vector<node>v[N];
void dfs(int fa,int u,int a,int b){
//    cout<<"j"<<fa<<" "<<u<<" "<<a<<" "<<b;
    if(u==n){
        flag=1;
        s1=min(s1,a);
        s2=min(s2,b);
//        cout<<s1<<" "<<s2<<endl;
        return;
    }
    for(auto ed:v[u]){
        int v=ed.v;
        int w1=ed.w1;
        int w2=ed.w2;
//        cout<<u<<" "<<v<<" "<<w1<<" "<<w2<<endl;
        if(v==fa)continue;
        if(v==u)continue;
        if(mk[v])continue;
        mk[v]=1;
        w1=max(w1,a);
        w2=max(w2,b);
        dfs(u,v,w1,w2);
        mk[v]=0;
    }
}
int main(){
    freopen("magicalforest.in","r",stdin);
    freopen("magicalforest.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,a,b;
        cin>>x>>y>>a>>b;
        v[x].push_back({y,a,b});
        v[y].push_back({x,a,b});
    }
    dfs(-1,1,-1,-1);
    if(!flag)cout<<-1;
    else cout<<s1+s2;
    return 0;
}