#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
int n,m;
ll ans=1e18;
int u,v,w1,w2;
int h[50005],to[200005],nxt[200005],val1[200005],val2[200005];
bool b[50005];
int cnt;
void add(int a,int b,int v1,int v2){
    to[++cnt]=b;
    val1[cnt]=v1;
    val2[cnt]=v2;
    nxt[cnt]=h[a];
    h[a]=cnt;
}
void dfs(int u,int v1,int v2){
    if(u==n){
        ans=min(ans,(long long)v1+v2);
        return;
    }
    for(int i=h[u];i;i=nxt[i]){
        int v=to[i];
        if(!b[v]){
            b[v]=1;
            dfs(v,max(val1[i],v1),max(val2[i],v2));
            b[v]=0;
        }
    }
}
int main(){
    freopen("magicalforest.in","r",stdin);
    freopen("magicalforest.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d%d",&u,&v,&w1,&w2);
        add(u,v,w1,w2);
        add(v,u,w1,w2);
    }
    dfs(1,0,0);
    if(ans!=1e9)
        printf("%d",ans);
    else
        printf("-1");
    return 0;
}