#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 int lmt=202;
ll dis[lmt][lmt],E[lmt],to[lmt],n,m,dis2[lmt];
bool block[lmt];
vector<array<ll,3>>adj[lmt];
void dij(int x){
for(int i=1;i<=n;i++){
dis2[i]=1e15;
to[i]=E[i]=0;
}
dis2[x]=0;
set<pair<ll,ll>>q;
q.insert({0,x});
while(!q.empty()){
auto it=q.begin();
ll val=(*it).first,u=(*it).second;
q.erase(it);
if(dis2[u]<val) continue;
for(auto z:adj[u]){
ll w=z[0],v=z[1],idx=z[2];
if(block[idx]) continue;
if(dis2[v]>dis2[u]+w){
dis2[v]=dis2[u]+w,to[v]=u,E[v]=idx;
q.insert({dis2[v],v});
}
}
}
return;
}
int main(){
fastio;
cin>>n>>m;
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++) dis[i][j]=1e15;
dis[i][i]=0;
}
vector<array<ll,4>>e;
for(int i=1;i<=m;i++){
ll u,v,c,d;
cin>>u>>v>>c>>d;
e.push_back({u,v,c,d});
dis[u][v]=min(dis[u][v],c);
adj[u].push_back({c,v,i});
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
ll ans=dis[1][n]+dis[n][1];
dij(1);
int x=n;
map<int,bool>used;
if(dis2[n]<1e15){
while(x>1){
used[E[x]]=1,x=to[x];
}
}
x=1;
dij(n);
if(dis2[1]<1e15){
while(x<n){
used[E[x]]=1,x=to[x];
}
}
for(int i=1;i<=m;i++){
if(used[i]) continue;
ll u=e[i-1][0],v=e[i-1][1],c=e[i-1][2],d=e[i-1][3];
ans=min(ans,dis[1][n]+dis[n][v]+c+d+dis[u][1]);
ans=min(ans,dis[1][v]+c+d+dis[u][n]+dis[n][1]);
ans=min(ans,dis[1][v]+c+d+dis[u][n]+dis[n][v]+c+d+dis[u][1]);
}
int last=m;
for(int i=1;i<=m;i++){
if(!used[i]) continue;
ll u=e[i-1][0],v=e[i-1][1],c=e[i-1][2],d=e[i-1][3];
block[i]=1;
adj[v].push_back({c,u,++last});
ll res=d;
dij(1);
res+=dis2[n];
dij(n);
res+=dis2[1];
ans=min(ans,res);
block[last]=1;
}
cout<<(ans>=1e15?-1:ans)<<endl;
return 0;
}
