#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=2e2+5;
const ll M=5e5+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<58);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
ll n,m,dis[N][N],dist[N][N],Front[N][N],x,y,c[M],d[M],ans1[M],vis[M],ans,DIS[N][N],ans2[M];
vector<ll> lis,nd;
pll ed[M];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
REP1(i,n)REP1(j,n)dis[i][j]=(i==j?0LL:INF);
REP1(i,m){
cin>>ed[i].X>>ed[i].Y>>c[i]>>d[i];
if(dis[ed[i].X][ed[i].Y]>c[i]){
Front[ed[i].X][ed[i].Y]=i;
dis[ed[i].X][ed[i].Y]=c[i];
}
}
REP1(k,n)REP1(i,n)REP1(j,n){
if(dis[i][k]+dis[k][j]<dis[i][j]){
dis[i][j]=dis[i][k]+dis[k][j];
Front[i][j]=Front[i][k];
}
}
ans=dis[1][n]+dis[n][1];
x=1;nd.pb(x);
while(Front[x][n]){
vis[Front[x][n]]=1;
lis.pb(Front[x][n]);
x=ed[Front[x][n]].Y;
nd.pb(x);
}
REP1(i,n)REP1(j,n)dist[i][j]=(i==j?0:INF);
REP1(i,m){
if(!vis[i]){
ans1[i]=min(dis[1][n],dis[1][ed[i].Y]+c[i]+dis[ed[i].X][n]);
dist[ed[i].X][ed[i].Y]=min(dist[ed[i].X][ed[i].Y],c[i]);
}
}
REP1(k,n)REP1(i,n)REP1(j,n)dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
for(ll id:lis){
for(ll i=SZ(nd)-1,suf=INF;;i--){
suf=min(suf,dist[nd[i]][ed[id].Y]);
DIS[nd[i]][ed[id].Y]=(nd[i]==ed[id].Y?0:suf);
suf+=dis[nd[i-1]][nd[i]];
if(nd[i]==ed[id].Y)break;
}
for(ll i=0;;i++){
for(ll j=SZ(nd)-1;;j--){
DIS[nd[i]][n]=dist[nd[i]][nd[j]]+dis[nd[j]][n];
if(nd[j]==ed[id].Y)break;
}
if(nd[i]==ed[id].X)break;
}
for(ll i=0;;i++){
for(ll j=SZ(nd)-1;;j--){
ans1[id]=min(dis[1][nd[i]]+dist[nd[i]][nd[j]]+dis[nd[j]][n],dis[1][nd[i]]+dist[nd[i]][nd[j]]+DIS[nd[j]][ed[i].Y]+c[id]+DIS[ed[i].X][n]);
if(nd[j]==ed[id].Y)break;
}
if(nd[i]==ed[id].X)break;
}
}
lis.clear();nd.clear();memset(vis,0,sizeof(vis));
x=n;nd.pb(x);
while(Front[x][1]){
vis[Front[x][1]]=1;
lis.pb(Front[x][1]);
x=ed[Front[x][1]].Y;
nd.pb(x);
}
REP1(i,n)REP1(j,n)dist[i][j]=(i==j?0:INF);
REP1(i,m){
if(!vis[i]){
ans2[i]=min(dis[n][1],dis[n][ed[i].Y]+c[i]+dis[ed[i].X][1]);
dist[ed[i].X][ed[i].Y]=min(dist[ed[i].X][ed[i].Y],c[i]);
}
}
REP1(k,n)REP1(i,n)REP1(j,n)dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
for(ll id:lis){
for(ll i=SZ(nd)-1,suf=INF;;i--){
suf=min(suf,dist[nd[i]][ed[id].Y]);
DIS[nd[i]][ed[id].Y]=(nd[i]==ed[id].Y?0:suf);
suf+=dis[nd[i-1]][nd[i]];
if(nd[i]==ed[id].Y)break;
}
for(ll i=0;;i++){
for(ll j=SZ(nd)-1;;j--){
DIS[nd[i]][1]=dist[nd[i]][nd[j]]+dis[nd[j]][1];
if(nd[j]==ed[id].Y)break;
}
if(nd[i]==ed[id].X)break;
}
for(ll i=0;;i++){
for(ll j=SZ(nd)-1;;j--){
ans2[id]=min(dis[n][nd[i]]+dist[nd[i]][nd[j]]+dis[nd[j]][1],dis[n][nd[i]]+dist[nd[i]][nd[j]]+DIS[nd[j]][ed[i].Y]+c[id]+DIS[ed[i].X][1]);
if(nd[j]==ed[id].Y)break;
}
if(nd[i]==ed[id].X)break;
}
}
REP1(i,m)ans=min(ans,ans1[i]+ans2[i]+d[i]);
cout<<(ans>=INF?-1:ans)<<"\n";
return 0;
}
