#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 2e9;
const int N = 2e2 + 5;
int n, m, a[N];
int d[3][N][N], cost[N], curd[N], p[N];
vector<int >g[N];
vector<int >path1,path2;
priority_queue<pair<long long,long long>>q;
bool is[2][N];
struct edge{
int u,v,c,d;
};
vector<edge>e;
inline void recover(int v,vector<int >&path){
path.push_back(p[v]);
v=e[p[v]].u;
while(v!=1&&v!=n){
path.push_back(p[v]);
v=e[p[v]].u;
}
reverse(path.begin(),path.end());
}
void dxtra(int s){
fill(curd,curd+N,inf);
q.push(make_pair(0,s));
curd[s]=p[s]=0;
while(!q.empty()){
int d=-q.top().first,v=q.top().second;
q.pop();
if(d>curd[v])
continue;
for(int ind:g[v]){
int to=e[ind].v,w=e[ind].c;
if(curd[to]>curd[v]+w){
p[to]=ind;
curd[to]=curd[v]+w;
q.push(make_pair(-curd[to],to));
}
}
}
}
void calc_distance(){
for(int i=0;i<2;++i)
for(int j=0;j<N;++j)
for(int k=0;k<N;++k){
if(j!=k)
d[i][j][k]=inf;
}
for(int i=0;i<m;++i)
d[0][e[i].u][e[i].v]=min(d[0][e[i].u][e[i].v],e[i].c);
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
d[0][i][j]=min(d[0][i][j],d[0][i][k]+d[0][k][j]);
for(int t=0;t<2;++t){
for(int i=0;i<m;++i)
if(!is[t][i])
d[t+1][e[i].u][e[i].v]=min(d[t+1][e[i].u][e[i].v],e[i].c);
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
d[t+1][i][j]=min(d[t+1][i][j],d[t+1][i][k]+d[t+1][k][j]);
}
}
signed main(){
cin>>n>>m;
for(int i=0;i<m;++i){
int u,v,cc,dd;
cin>>u>>v>>cc>>dd;
g[u].push_back(i);
e.push_back({u,v,cc,dd});
}
dxtra(1);
if(curd[n]!=inf)
recover(n,path1);
dxtra(n);
if(curd[1]!=inf)
recover(1,path2);
for(int ind:path1)
is[0][ind]=true;
for(int ind:path2)
is[1][ind]=true;
calc_distance();
for(int i=0;i<m;++i){
int u=e[i].u,v=e[i].v,c=e[i].c;
if(!is[0][i]){
cost[i]+=min(d[0][1][n],d[0][1][v]+d[0][u][n]);
}
else{
int j=0;
for(j=0;j<path1.size();++j)
if(i==path1[j])
break;
int now=inf;
for(int i=0;i<=j;++i){
for(int k=j;k<path1.size();++k){
int u=e[i].u,v=e[k].v;
now=min(now,d[0][1][u]+d[1][u][v]+d[0][v][n]);
}
}
cost[i]+=now;
}
}
for(int i=0;i<m;++i){
int u=e[i].u,v=e[i].v,c=e[i].c;
if(!is[1][i]){
cost[i]+=min(d[0][n][1],d[0][n][v]+d[0][u][1]);
}
else{
int j=0;
for(j=0;j<path2.size();++j)
if(i==path2[j])
break;
int now=inf;
for(int i=0;i<=j;++i)
for(int k=j;k<path2.size();++k){
int u=e[i].u,v=e[k].v;
now=min(now,d[0][n][u]+d[2][u][v]+d[0][v][1]);
}
cost[i]+=now;
}
}
int ans=d[0][1][n]+d[0][n][1];
for(int i=0;i<m;++i)
ans=min(ans,cost[i]+e[i].c+e[i].d);
if(ans>=inf)
cout<<-1<<endl;
else
cout<<ans<<endl;
return 0;
}
