#include <bits/stdc++.h>
//#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N=5e4+5;
vector <pair <pair <int,int> ,int> > g[2][205];
int p[4][205],dis[4][205],dist[205];
int a[N],b[N],c[N],d[N],used[N];
priority_queue <pair <int,int> > pq;
void djkstra(int n,int tp,int x){
dis[x][n]=0;
pq.push({0,n});
while(!pq.empty()){
int v=pq.top().ss;
pq.pop();
for(auto to : g[tp][v]){
if(dis[x][to.ff.ff]>dis[x][v]+to.ff.ss){
dis[x][to.ff.ff]=dis[x][v]+to.ff.ss;
p[x][to.ff.ff]=to.ss;
pq.push({dis[x][to.ff.ff],to.ff.ff});
}
}
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>a[i]>>b[i]>>c[i]>>d[i];
g[0][a[i]].pb({{b[i],c[i]},i});
g[1][b[i]].pb({{a[i],c[i]},i});
}
for(int i=1;i<=n;i++){
for(int j=0;j<4;j++){
dis[j][i]=1e9;
}
}
djkstra(1,0,0);
djkstra(1,1,1);
djkstra(n,0,2);
djkstra(n,1,3);
/*for(int x=0;x<4;x++){
for(int i=1;i<=n;i++){
cout<<dis[x][i]<<" ";
}
cout<<"\n";
}
cout<<"\n";*/
for(int x=0;x<4;x++){
for(int i=1;i<=n;i++){
used[p[x][i]]=1;
}
}
int mn=2e9;
if(dis[0][n]<1e9 && dis[2][1]<1e9)mn=min(dis[0][n]+dis[2][1],mn);
for(int i=1;i<=m;i++){
if(!used[i]){
int new1n=min(dis[0][n],dis[0][b[i]]+dis[3][a[i]]+c[i]);
int newn1=min(dis[2][1],dis[2][b[i]]+dis[1][a[i]]+c[i]);
if(new1n<1e9 && newn1<1e9)mn=min(mn,new1n+newn1+d[i]);
}
else{
for(int j=1;j<=n;j++){
dist[j]=1e9;
}
dist[1]=0;
pq.push({0,1});
while(!pq.empty()){
int v=pq.top().ss;
pq.pop();
if(v==b[i]){
if(dist[a[i]]>dist[b[i]]+c[i]){
dist[a[i]]=dist[b[i]]+c[i];
pq.push({dist[a[i]],a[i]});
}
}
for(auto to : g[0][v]){
if(to.ss==i)continue;
if(dist[to.ff.ff]>dist[v]+to.ff.ss){
dist[to.ff.ff]=dist[v]+to.ff.ss;
pq.push({dist[to.ff.ff],to.ff.ff});
}
}
}
if(dist[n]<1e9){
int ans=dist[n];
for(int j=1;j<=n;j++){
dist[j]=1e9;
}
dist[n]=0;
pq.push({0,n});
while(!pq.empty()){
int v=pq.top().ss;
pq.pop();
if(v==b[i]){
if(dist[a[i]]>dist[b[i]]+c[i]){
dist[a[i]]=dist[b[i]]+c[i];
pq.push({dist[a[i]],a[i]});
}
}
for(auto to : g[0][v]){
if(to.ss==i)continue;
if(dist[to.ff.ff]>dist[v]+to.ff.ss){
dist[to.ff.ff]=dist[v]+to.ff.ss;
pq.push({dist[to.ff.ff],to.ff.ff});
}
}
}
if(dist[1]<1e9)mn=min(mn,ans+dist[1]+d[i]);
}
}
}
if(mn==2e9)mn=-1;
cout<<mn<<"\n";
}
//g[1]-r
//dis[0] 1
//dis[1] 1r
//dis[2] n
//dis[3] nr
/*
*/
