#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
#define ckmin(a, b) a = min(a, b)
#define ckmax(a, b) a = max(a, b)
const int maxn = 4e5 + 5;
const ll INF = 2e9 + 7;
struct edge{
int a, b, c, d;
edge(){}
edge(int _a, int _b, int _c, int _d) : a(_a), b(_b), c(_c), d(_d){}
};
int n, m;
vector<int> adj[maxn], radj[maxn];
vector<edge> e;
int invalid[50004], crit[50004];
int main(void){
fastio;
cin>>n>>m;
for(int i = 0; i < m; i++){
int a, b, c, d;
cin>>a>>b>>c>>d;
a--, b--;
adj[a].pb(i);
radj[b].pb(i);
e.pb(edge(a, b, c, d));
}
vector<ll> dist(n, INF), dist2(n, INF), rdist(n, INF), rdist2(n, INF);
vector<int> from(n), from2(n);
dist[0] = 0, dist2[n - 1] = 0, rdist[n - 1] = 0, rdist2[0] = 0;
auto dijkstra = [&](vector<ll>& dist, vector<int>& from) -> void{
vector<int> vis(n);
for(int i = 0; i < n; i++){
ll mn = INF, id = 0;
for(int j = 0; j < n; j++) if(!vis[j] && dist[j] < mn) mn = dist[j], id = j;
vis[id] = 1;
for(auto x : adj[id]){
if(invalid[x]) continue;
auto [a, b, c, d] = e[x];
if(dist[b] > dist[a] + c) from[b] = a;
dist[b] = min(dist[b], dist[a] + c);
}
}
};
auto rdijkstra = [&](vector<ll>& dist) -> void{
vector<int> vis(n);
for(int i = 0; i < n; i++){
ll mn = INF, id = 0;
for(int j = 0; j < n; j++) if(!vis[j] && dist[j] < mn) mn = dist[j], id = j;
vis[id] = 1;
for(auto x : radj[id]){
auto [a, b, c, d] = e[x];
dist[a] = min(dist[a], dist[b] + c);
}
}
};
dijkstra(dist, from);
dijkstra(dist2, from2);
rdijkstra(rdist);
rdijkstra(rdist2);
auto find_crit = [&](int st, int ed, vector<ll> &dist, vector<int> &from){
if(dist[ed] >= INF) return;
int pos = ed;
while(pos != st){
int org = pos;
for(auto x : radj[pos]){
auto [a, b, c, d] = e[x];
if(dist[pos] == dist[a] + c && from[pos] == a){
crit[x] = 1;
pos = a;
break;
}
}
}
};
find_crit(0, n - 1, dist, from);
find_crit(n - 1, 0, dist2, from2);
ll ans = dist[n - 1] + dist2[0];
int cnt = 0;
for(int i = 0; i < m; i++){
auto [a, b, c, d] = e[i];
if(crit[i]){
cnt++;
if(cnt > n * 2) break;
// if(cnt > n * 10) break;
invalid[i] = 1;
e.pb(edge(b, a, c, d));
adj[b].pb(m);
vector<ll> ndist(n, INF), ndist2(n, INF);
ndist[0] = 0, ndist2[n - 1] = 0;
dijkstra(ndist, from), dijkstra(ndist2, from);
ans = min(ans, ndist[n - 1] + ndist2[0] + d);
e.pop_back();
adj[b].pop_back();
invalid[i] = 0;
continue;
}
//invert : becomes b->a
ll d1 = min(dist[n - 1], dist[b] + rdist[a] + c);
ll d2 = min(dist2[0], dist2[b] + rdist2[a] + c);
ans = min(ans, d1 + d2 + d);
}
cout<<(ans < INF ? ans : -1)<<"\n";
}
