#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX
const ll lmt=201;
vector<array<ll,3>>adj[lmt];
ll dis[lmt][lmt][2],node[lmt][lmt],e[lmt][lmt];
int main(){
fastio;
ll n,m;
cin>>n>>m;
for(ll i=0;i<=n;i++){
for(ll j=0;j<=n;j++) for(ll k=0;k<2;k++) dis[i][j][k]=1e17;
}
vector<array<ll,3>>inv;
for(ll i=1;i<=m;i++){
ll u,v,c,d;
cin>>u>>v>>c>>d;
inv.push_back({v,u,c+d});
adj[u].push_back({c,v,i});
}
for(ll x=1;x<=n;x++){
dis[x][x][0]=0;
set<array<ll,3>>q;
q.insert({0,x,0});
while(!q.empty()){
auto it=q.begin();
ll val=(*it)[0],u=(*it)[1],ver=(*it)[2];
q.erase(it);
if(dis[x][u][ver]<val) continue;
for(auto p:adj[u]){
ll w=p[0],v=p[1],idx=p[2];
if(dis[x][v][0]>dis[x][u][ver]+w){
dis[x][v][0]=dis[x][u][ver]+w,node[x][v]=u,e[x][v]=idx;
q.insert({dis[x][v][0],v,0});
}else if(dis[x][v][1]>dis[x][u][ver]+w){
dis[x][v][1]=dis[x][u][ver]+w;
q.insert({dis[x][v][1],v,1});
}
}
}
}
ll ans=dis[1][n][0]+dis[n][1][0];
//cout<<dis[1][n][0]<<" "<<dis[n][1][0]<<endl;
if(dis[1][n][0]<1e17){
ll x=n;
map<ll,bool>used;
while(x>1){
used[e[1][x]]=1,x=node[1][x];
}
for(ll i=1;i<=m;i++){
ll u=inv[i-1][0],v=inv[i-1][1],val=inv[i-1][2],res;
if(used[i]){
res=dis[1][v][0]+dis[u][n][0]+dis[v][u][1]+dis[n][u][0]+val+dis[v][1][0];
}else{
res=dis[1][n][0]+dis[n][u][0]+val+dis[v][1][0];
}
ans=min(ans,res);
}
}
if(dis[n][1][0]<1e17){
ll x=1;
map<ll,bool>used;
while(x<n){
used[e[n][x]]=1,x=node[n][x];
}
for(ll i=1;i<=m;i++){
ll u=inv[i-1][0],v=inv[i-1][1],val=inv[i-1][2],res;
if(used[i]){
res=dis[n][v][0]+dis[u][1][0]+dis[v][u][1]+dis[1][u][0]+val+dis[v][n][0];
}else{
res=dis[n][1][0]+dis[1][u][0]+val+dis[v][n][0];
}
ans=min(ans,res);
}
}
cout<<(ans>=1e17?-1:ans)<<endl;
return 0;
}
