#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
typedef long long ll;
#define x first
#define y second
int n,m;
vector<vector<pair<int,int>>> G,GT,GC1,GC2;
vector<pair<int,int>> C;
vector<pair<int,int>> A;
vector<ll> CMC1(int ini)
{
priority_queue<pair<ll,int>>q;
vector<ll> v(n+1,1e16);
q.push({0,ini});
int pl=n;
if(ini==n) pl=1;
while(!q.empty())
{
pair<ll,int> node=q.top();q.pop();
if(v[node.y]==1e16)
{
v[node.y]=-node.x;
if(node.y!=pl)
for(auto i:G[node.y])
if(v[i.x]==1e16)
q.push({node.x-C[i.y].x,i.x});
}
}
return v;
}
vector<ll> CMC2(int ini)
{
priority_queue<pair<ll,int>>q;
q.push({0,ini});
vector<ll> v(n+1,1e16);
int pl=n;
if(ini==n) pl=1;
while(!q.empty())
{
pair<ll,int> node=q.top();q.pop();
if(v[node.y]==1e16)
{
v[node.y]=-node.x;
if(node.y!=pl)
for(auto i:GT[node.y])
if(v[i.x]==1e16)
q.push({node.x-C[i.y].x,i.x});
}
}
return v;
}
vector<int>ord1,ord2;
vector<int>B1,B2;
int cnt1=1,cnt2=1;
void P1(int node, int P)
{
if(ord1[node]!=0) return;
int ordent=cnt1;
ord1[node]=cnt1++;
for(auto i:GC1[node])
{
if(i.x!=P){
P1(i.x,node);
if(ord1[i.x]>ord1[node]) B1[i.y]=1;
ordent=min(ordent,ord1[i.x]);
}
}
ord1[node]=ordent;
}
void P2(int node, int P)
{
if(ord2[node]!=0) return;
int ordent=cnt2;
ord2[node]=cnt2++;
for(auto i:GC2[node])
{
if(i.x!=P)
{
P2(i.x,node);
if(ord2[i.x]>ord2[node]) B2[i.y]=1;
ordent=min(ordent,ord2[i.x]);
}
}
ord2[node]=ordent;
}
ll CMC3(ll ini, ll fin, ll e)
{
priority_queue<pair<ll,int>>q;
vector<ll> v(n+1,1e16);
q.push({0,ini});
while(!q.empty())
{
pair<ll,ll> node=q.top();q.pop();
if(node.y==fin) return -node.x;
if(v[node.y]==1e16)
{
v[node.y]=-node.x;
for(auto i:G[node.y])
if(v[i.x]==1e16&&i.y!=e)
q.push({node.x-C[i.y].x,i.x});
}
}
return 1e16;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
A.resize(m);
C.resize(m);
G.resize(n+1);
GT.resize(n+1);
for(int i=0; i<m; i++)
{
int a,b;
cin>>a>>b>>C[i].x>>C[i].y;
G[a].push_back({b,i});
GT[b].push_back({a,i});
A[i]={a,b};
}
GC1.resize(n+1);
GC2.resize(n+1);
vector<ll> D1=CMC1(1),DT1=CMC2(1);
vector<ll> DN=CMC1(n),DTN=CMC2(n);
for(int i=0; i<m; i++)
{
if(D1[A[i].x]+DTN[A[i].y]+C[i].x==D1[n]&&D1[n]!=1e16) GC1[A[i].x].push_back({A[i].y,i});
if(DN[A[i].x]+DT1[A[i].y]+C[i].x==DN[1]&&DN[1]!=1e16) GC2[A[i].x].push_back({A[i].y,i});
}
ord1.assign(n+1,0);
ord2.assign(n+1,0);
B1.assign(m+1,0);
B2.assign(m+1,0);
P1(1,0);
P2(n,0);
ll bs=D1[n]+DN[1];
for(int i=0; i<m; i++)
{
if(B1[i]==0&&B2[i]==0)
{
bs=min(bs,(min(DN[1],DN[A[i].y]+DT1[A[i].x]+C[i].x)+D1[A[i].y]+DTN[A[i].x]+C[i].x+C[i].y));
bs=min(bs,(min(D1[n],D1[A[i].y]+DTN[A[i].x]+C[i].x)+DN[A[i].y]+DT1[A[i].x]+C[i].x+C[i].y));
}
}
for(int i=0; i<m; i++)
{
if(B1[i]==0&&B2[i]==0)continue;
if(DN[A[i].y]+DT1[A[i].x]+C[i].x+C[i].y<bs&&B1[i]==1)
bs=min(bs,(CMC3(1,n,i)+DN[A[i].y]+DT1[A[i].x]+C[i].x+C[i].y));
if(D1[A[i].y]+DTN[A[i].x]+C[i].x+C[i].y<bs&&B2[i]==1)
bs=min(bs,(CMC3(n,1,i)+D1[A[i].y]+DTN[A[i].x]+C[i].x+C[i].y));
}
if(bs>1e15)
{
cout<<-1;
return 0;
}
cout<<bs;
return 0;
}
