#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;
const int N=207,M=50007;
struct edge
{
int u,id;
ll c,d;
};
vector<edge>G[N][2];
int n,m;
bool is[M];
int o[N],k[N];
vector<ll> dijkstra(int p,int ban,int c)
{
vector<ll>d(n+1,infl);
vector<bool>odw(n+1,0);
memset(o,0,sizeof o);
memset(k,0,sizeof k);
d[p]=0;
while(true)
{
int v;
ll mn=infl;
for(int i=1;i<=n;i++)
{
if(!odw[i]&&d[i]<mn)
{
v=i;
mn=d[i];
}
}
if(mn==infl) break;
odw[v]=1;
for(auto e:G[v][c])
{
if(e.id==ban) continue;
if(d[v]+e.c<d[e.u])
{
d[e.u]=d[v]+e.c;
o[e.u]=v;
k[e.u]=e.id;
}
}
}
return d;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v;
ll c,d;
cin>>u>>v>>c>>d;
G[u][0].pb({v,i,c,d});
G[v][1].pb({u,i,c,d});
}
vector<ll>D1=dijkstra(1,-1,0);
for(int i=1;i<=n;i++)
{
int x=i;
if(D1[i]==infl) x=0;
while(x)
{
is[k[x]]=1;
x=o[x];
}
}
vector<ll>D1r=dijkstra(1,-1,1);
for(int i=1;i<=n;i++)
{
int x=i;
if(D1r[i]==infl) x=0;
while(x)
{
is[k[x]]=1;
x=o[x];
}
}
vector<ll>Dn=dijkstra(n,-1,0);
for(int i=1;i<=n;i++)
{
int x=i;
if(Dn[i]==infl) x=0;
while(x)
{
is[k[x]]=1;
x=o[x];
}
}
vector<ll>Dnr=dijkstra(n,-1,1);
for(int i=1;i<=n;i++)
{
int x=i;
if(Dnr[i]==infl) x=0;
while(x)
{
is[k[x]]=1;
x=o[x];
}
}
ll ans=min(infl,D1[n]+Dn[1]);
for(int v=1;v<=n;v++)
{
for(auto e:G[v][0])
{
if(is[e.id])
{
G[e.u][0].pb({v,-1,e.c,e.d});
vector<ll>neD1=dijkstra(1,e.id,0);
vector<ll>neDn=dijkstra(n,e.id,0);
G[e.u][0].pop_back();
ans=min(ans,neD1[n]+neDn[1]+e.d);
}
else
{
ll X=D1[e.u]+Dnr[v]+e.c,Y=Dn[e.u]+D1r[v]+e.c;
ans=min(ans,X+e.d+min(Dn[1],Y));
ans=min(ans,Y+e.d+min(X,D1[n]));
}
}
}
if(ans==infl) cout<<-1;
else cout<<ans;
return 0;
}
