#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;
const int inf=4e18;
struct eg{
int v,id,c,d;
};
vector<vector<eg> > e;
vector<int> p[2];
vector<int> dz[2];
int n;
int dijk(int x,int y,int t){
p_q<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
vector<int> dis(n,inf);
dis[x]=0;
pq.push({0,x});
while(!pq.empty()){
auto h=pq.top();
pq.pop();
if(dis[h.sc]!=h.fs){
continue;
}
for(auto a:e[h.sc]){
if(dis[a.v]>dis[h.sc]+a.c){
dis[a.v]=dis[h.sc]+a.c;
if(t<2){
p[t][a.v]=a.id;
}
pq.push({dis[a.v],a.v});
}
}
}
if(t<2){
dz[t]=dis;
}
assert(dis[y]<=inf);
return dis[y];
}
pair<vector<int>,vector<int> > fw(vector<vector<int> >& ez){
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
ez[i][j]=min(ez[i][j],ez[i][k]+ez[k][j]);
}
}
}
vector<int> d1(n),d2(n);
for(int i=0;i<n;i++){
d1[i]=ez[i][n-1];
d2[i]=ez[i][0];
}
return {d1,d2};
}
signed main(){
AquA;
int m;
cin >> n >> m;
e.resize(n);
p[0].resize(n,-1);
p[1].resize(n,-1);
vector<vector<int> > ez(n,vector<int>(n,inf));
for(int i=0;i<m;i++){
int u,v,c,d;
cin >> u >> v >> c >> d;
u--;
v--;
e[u].push_back({v,i+1,c,d});
ez[u][v]=min(ez[u][v],c);
}
for(int i=0;i<n;i++){
ez[i][i]=0;
}
vector<int> to[2];
//to[0].resize(n);
//to[1].resize(n);
auto tmp=fw(ez);
to[0]=tmp.fs;
to[1]=tmp.sc;
int ans=inf;
ans=min(inf,dijk(0,n-1,0)+dijk(n-1,0,1));
for(int i=0;i<n;i++){
for(int j=0;j<e[i].size();j++){
auto h=e[i][j];
e[h.v].push_back({i,-1,h.c+h.d,-1});
e[i][j].c+=2*inf;
ans=min(ans,dijk(0,n-1,2)+dijk(n-1,0,2));
e[i][j].c-=2*inf;
auto y=e[h.v].back();
assert(y.v==i && y.id==-1 && y.c==h.c+h.d && y.d==-1);
e[h.v].pop_back();
}
}
if(ans>=inf){
cout << -1 << "\n";
}
else{
cout << ans << "\n";
}
return 0;
}
