#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int MAXN = 5e4+5;
const ll INF = 1e18;
#define sz(a) (int)(a.size())
ll c[MAXN],d[MAXN];
int n,m;
array<int,2>spar[201],tpar[201],par[201];
vector<array<int,2>>g[201],gr[201];
bool block[MAXN],vis[201];
//distances
ll dist[201];
ll from_s[201],from_t[200];
ll to_s[201],to_t[200];
void djikstra(int v,vector<array<int,2>>*g,ll *dist,array<int,2>*par){
dist[0] = INF;
for(int i=1;i<=n;i++)dist[i] = INF,vis[i] = 0;
dist[v] = 0;
while(true){
int u = 0;
for(int i=1;i<=n;i++)if(dist[i] < dist[u] && !vis[i])u = i;
if(!u)break;
vis[u] = 1;
for(auto x:g[u]){
if(block[x[1]])continue;
if(dist[u] + c[x[1]] < dist[x[0]]){
dist[x[0]] = dist[u] + c[x[1]];
par[x[0]] = {u,x[1]};
}
}
}
}
ll s_to_t[2][MAXN],t_to_s[2][MAXN];
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
vector<array<int,2>>edge;
for(int i=0;i<m;i++){
int v,u;
cin>>v>>u>>c[i]>>d[i];
g[v].push_back({u,i});
gr[u].push_back({v,i});
edge.push_back({v,u});
}
djikstra(1,g,from_s,spar);
ll none = from_s[n];
for(int i=0;i<m;i++)s_to_t[0][i] = from_s[n];
//first case not use inverted path at all
//some might intersect so bad
if(from_s[n] != INF){
int cur = n;
while(cur != 1){
int p = spar[cur][1];
block[p] = 1;
djikstra(1,g,dist,par);
s_to_t[0][p] = dist[n];
block[p] = 0;
cur = spar[cur][0];
}
}
//second case invert v->u
//use 1->u->v then v->n
//1->u can't use 1->v->u since v->u can only be the last edge only need to consider another last edge if v->u just happens to be used in best path
//v->n cant use v->u->n can be treated similarly as 1->u
djikstra(n,gr,to_t,tpar);
for(int i=0;i<m;i++){
int v = edge[i][0],u = edge[i][1];
ll cost = from_s[u] + to_t[v] + c[i];
if(spar[u][1] == i){
cost-=from_s[u];
block[spar[u][1]] = 1;
djikstra(1,g,dist,par);
cost+=dist[u];
block[spar[u][1]] = 0;
}
if(tpar[v][1] == i){
cost-=to_t[v];
block[tpar[v][1]] = 1;
djikstra(n,gr,dist,par);
cost+=dist[v];
block[tpar[v][1]] = 0;
}
s_to_t[1][i] = cost;
}
///////////// n->t;
djikstra(n,g,from_t,tpar);
none+=from_t[1];
for(int i=0;i<m;i++)t_to_s[0][i] = from_t[1];
if(from_t[1] != INF){
int cur = 1;
while(cur != n){
int p = tpar[cur][1];
block[p] = 1;
djikstra(n,g,dist,par);
t_to_s[0][p] = dist[1];
block[p] = 0;
cur = tpar[cur][0];
}
}
djikstra(1,gr,to_s,spar);
for(int i=0;i<m;i++){
int v = edge[i][0],u = edge[i][1];
ll cost = from_t[u] + to_s[v] + c[i];
if(tpar[u][1] == i){
cost-=from_t[u];
block[tpar[u][1]] = 1;
djikstra(n,g,dist,par);
cost+=dist[u];
block[tpar[u][1]] = 0;
}
if(spar[v][1] == i){
cost-=to_s[v];
block[spar[v][1]] = 1;
djikstra(1,gr,dist,par);
cost+=dist[v];
block[spar[v][1]] = 0;
}
t_to_s[1][i] = cost;
}
ll ans = min(INF,none);
for(int i=0;i<m;i++){
ans = min(ans,s_to_t[0][i] + t_to_s[0][i]);
ans = min(ans,min(s_to_t[1][i],s_to_t[0][i]) + min(t_to_s[1][i],t_to_s[0][i]) + d[i]);
}
if(ans == INF)ans=-1;
cout<<ans<<'\n';
}
