#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 long long inf=4.9e17;
struct eg{
int v,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> > 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]=h.sc;
}
pq.push({dis[a.v],a.v});
}
}
}
if(t<2){
dz[t]=dis;
}
return dis[y];
}
signed main(){
AquA;
int m;
cin >> n >> m;
e.resize(n);
p[0].resize(n);
p[1].resize(n);
for(int i=0;i<m;i++){
int u,v,c,d;
cin >> u >> v >> c >> d;
u--;
v--;
e[u].push_back({v,c,d});
}
vector<int> to[2];
to[0].resize(n);
to[1].resize(n);
for(int i=0;i<n;i++){
to[0][i]=dijk(i,n-1,2);
to[1][i]=dijk(i,0,2);
}
int ans=0;
ans+=dijk(0,n-1,0);
ans+=dijk(n-1,0,1);
/*
for(int i=0;i<n;i++){
cout << dz[0][i] << " ";
}
cout << "\n";
for(int i=0;i<n;i++){
cout << dz[1][i] << " ";
}
cout << "\n";
for(int i=0;i<n;i++){
cout << to[0][i] << " ";
}
cout << "\n";
for(int i=0;i<n;i++){
cout << to[1][i] << " ";
}
cout << "\n";
cout << "\n";
*/
for(int i=0;i<n;i++){
for(int j=0;j<e[i].size();j++){
auto h=e[i][j];
int yy=dz[0][n-1],kk=inf;
if(dz[0][h.v]+h.c+h.d<dz[0][i]){
yy=min(yy,dz[0][h.v]+h.c+h.d+to[0][i]);
if(yy<dz[0][n-1]){
if(p[1][h.v]==i){
e[i][j].c+=h.d;
kk=min(kk,yy+dijk(n-1,0,2));
e[i][j].c-=h.d;
}
else{
kk=min(kk,yy+dz[1][0]);
}
}
}
yy=dz[1][0];
if(dz[1][h.v]+h.c+h.d<dz[1][i]){
yy=min(yy,dz[1][h.v]+h.c+h.d+to[1][i]);
//cout << to[1][i] << "\n";
//cout << i << " " << h.v << " " << yy << "\n";
if(yy<dz[1][0]){
if(p[0][h.v]==i){
e[i][j].c+=h.d;
kk=min(kk,yy+dijk(0,n-1,2));
e[i][j].c-=h.d;
}
else{
kk=min(kk,yy+dz[0][n-1]);
}
}
}
ans=min(ans,kk);
}
}
if(ans>=inf){
cout << -1 << "\n";
}
else{
cout << ans << "\n";
}
return 0;
}
