#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const ll inf = 1e18;
const int MX = 5e4 + 5;
ll n, m, a[MX], b[MX], c[MX], d[MX], ans, chk[2][MX], mnd[2], d1, d2, D[4][205];
vector<pair<ll, ll>> adj[205], rev[205];
ll dijk(int s, int e, int f){
int t = n + 1 - s;
vector<ll> dist(n + 1, inf);
vector<int> E(n + 1, 0), vis(n + 1, 0);
dist[s] = 0;
while(1){
ll mn = inf, x;
for(int i = 1; i <= n; i++)
if(!vis[i] && dist[i] < mn) mn = dist[i], x = i;
if(mn == inf) break;
vis[x] = 1;
if(f == 1 || f == 3){
for(auto&[nx, ix] : rev[x])
if(ix != e && dist[x] + c[ix] < dist[nx]) dist[nx] = dist[x] + c[ix], E[nx] = ix;
}
else{
for(auto&[nx, ix] : adj[x])
if(ix != e && dist[x] + c[ix] < dist[nx]) dist[nx] = dist[x] + c[ix], E[nx] = ix;
}
}
if(f >= 4){
f -= 4;
if(dist[t] == inf) return inf;
for(int x = t; x != s; x = a[E[x]]) chk[f][E[x]] = 1;
}
else if(f >= 0) {
for(int i = 1; i <= n; i++) D[f][i] = dist[i];
}
return dist[t];
}
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 0; i < m; i++){
cin >> a[i] >> b[i] >> c[i] >> d[i];
adj[a[i]].emplace_back(b[i], i);
rev[b[i]].emplace_back(a[i], i);
}
dijk(1, -1, 0);
dijk(n, -1, 1);
dijk(n, -1, 2);
dijk(1, -1, 3);
mnd[0] = dijk(1, -1, 4);
mnd[1] = dijk(n, -1, 5);
ans = mnd[0] + mnd[1];
for(int i = 0; i < m; i++){
adj[b[i]].emplace_back(a[i], m);
c[m] = c[i] + d[i];
if(!chk[0][i]) d1 = min(mnd[0], D[0][b[i]] + c[i] + d[i] + D[1][a[i]]);
else d1 = dijk(1, i, -1);
if(!chk[1][i]) d2 = min(mnd[1], D[2][b[i]] + c[i] + d[i] + D[3][a[i]]);
else d2 = dijk(n, i, -1);
//cout << d1 << ' ' << d2 << '\n';
ans = min(ans, d1 + d2);
adj[b[i]].pop_back();
}
cout << (ans >= inf ? -1 : ans);
return 0;
}
