#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 100'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 207;
const int K = 50'007;
pair<pair<int, int>, pair<int, int>> e[K];
vector<pair<int, pair<int, int>>> edf[N];
vector<pair<int, pair<int, int>>> edf2[N];
vector<pair<int, int>> ed[N], ed2[N];
vector<int> pth; int czy[K], czya[K];
ll dis[2 * N]; int vis[2 * N], sk[N];
int tab[N];
ll d1[N], d2[N];
ll f1[N], f2[N];
void DijkstraF(int n)
{
for(int i = 0; i <= n; ++i) {dis[i] = I; vis[i] = 0;}
dis[1] = 0;
while(true)
{
int v = 0;
for(int i = 1; i <= n; ++i)
if(!vis[i] && dis[i] < dis[v]) v = i;
if(v == 0) break;
vis[v] = 1;
for(int i = 0; i < (int)edf[v].size(); ++i)
{
ll o = dis[v] + (ll)edf[v][i].nd.st;
if(o < dis[edf[v][i].st])
{
dis[edf[v][i].st] = o; sk[edf[v][i].st] = edf[v][i].nd.nd;
}
}
}
int v = n;
if(dis[n] == I) return;
while(v != 1)
{
pth.pb(sk[v]);
czy[sk[v]] = 1; czya[sk[v]] = 1;
if(e[sk[v]].st.st != v) v = e[sk[v]].st.st;
else v = e[sk[v]].st.nd;
}
}
void Dijkstra(int n, int s)
{
for(int i = 0; i <= 2 * n; ++i) {dis[i] = I; vis[i] = 0;}
dis[s] = 0;
while(true)
{
int v = 0, u;
for(int i = 1; i <= 2 * n; ++i)
if(!vis[i] && dis[i] < dis[v]) v = i;
if(v == 0) break;
//cerr << v << " " << ed[v].size() << " " << ed2[v].size() << "\n";
vis[v] = 1;
u = v;
if(v > n) v -= n;
for(int i = 0; i < (int)ed[v].size(); ++i)
{
int ne = ed[v][i].st + (u - v);
ll d = dis[u] + (ll)ed[v][i].nd;
if(d < dis[ne])
dis[ne] = d;
}
if(u > n) continue;
for(int i = 0; i < (int)ed2[v].size(); ++i)
{
int ne = ed2[v][i].st + n;
ll d = dis[u] + (ll)ed2[v][i].nd;
if(d < dis[ne])
dis[ne] = d;
}
}
}
bool C(int a, int b)
{
if(d2[a] <= d2[b] && f2[a] <= f2[b] && d1[b] <= d1[a] && f1[b] <= f1[a])
return 1;
return 0;
}
ll Licz(int n, int m)
{
ll ans = I;
for(int i = 1; i <= n; ++i)
{ed[i].clear(); ed2[i].clear();}
for(int i = 1; i <= m; ++i)
ed[e[i].st.st].pb(make_pair(e[i].st.nd, e[i].nd.st));
Dijkstra(n, 1);
for(int i = 1; i <= n; ++i) d1[i] = dis[i];
Dijkstra(n, n);
for(int i = 1; i <= n; ++i) f1[i] = dis[i];
for(int i = 1; i <= n; ++i)
ed[i].clear();
for(int i = 1; i <= m; ++i)
ed[e[i].st.nd].pb(make_pair(e[i].st.st, e[i].nd.st));
Dijkstra(n, 1);
for(int i = 1; i <= n; ++i) d2[i] = dis[i];
Dijkstra(n, n);
for(int i = 1; i <= n; ++i) f2[i] = dis[i];
for(int i = 1; i <= m; ++i)
if(!czya[i])
if(C(e[i].st.st, e[i].st.nd))
{
ans = min(ans, d1[e[i].st.nd] + d2[e[i].st.st] + f1[e[i].st.nd] + f2[e[i].st.st] + 2LL * (ll)e[i].nd.st + (ll)e[i].nd.nd);
//cout << d1[e[i].st.nd] << " " << d2[e[i].st.st] << " " << f1[e[i].st.nd] << " " << f2[e[i].st.st] << "\n";
//cout << "ea: " << i << " " << ans << "\n";
}
return ans;
}
ll Try(int n, int m)
{
for(int i = 1; i <= n; ++i)
{ed[i].clear(); ed2[i].clear(); czy[i] = 0;}
pth.clear();
int a, b, c1, c2;
for(int i = 1; i <= m; ++i)
{
a = e[i].st.st; b = e[i].st.nd; c1 = e[i].nd.st; c2 = e[i].nd.nd;
edf[a].pb(make_pair(b, make_pair(c1, i)));
}
DijkstraF(n);
ll ans = I, cur = dis[n];
for(int i = 1; i <= m; ++i)
{
ed[e[i].st.st].pb(make_pair(e[i].st.nd, e[i].nd.st));
if(czy[i]) continue;
ed2[e[i].st.nd].pb(make_pair(e[i].st.st, e[i].nd.st + e[i].nd.nd));
}
Dijkstra(n, n);
cur += min(dis[1], dis[1 + n]);
ans = cur;
for(int l = 0; l < (int)pth.size(); ++l)
{
for(int i = 1; i <= n; ++i)
{ed[i].clear(); ed2[i].clear();}
for(int i = 1; i <= m; ++i)
{
if(i == pth[l])
ed2[e[i].st.nd].pb(make_pair(e[i].st.st, e[i].nd.st + e[i].nd.nd));
else
ed[e[i].st.st].pb(make_pair(e[i].st.nd, e[i].nd.st));
}
Dijkstra(n, 1);
cur = min(dis[n], dis[n + n]);
Dijkstra(n, n);
cur += min(dis[1], dis[1 + n]);
//cout << "C: " << l << " " << pth[l] << " " << cur << " " << ans << "\n";
ans = min(ans, cur);
}
return ans;
}
void Solve()
{
int n, m, a, b, c1, c2;
cin >> n >> m;
for(int i = 1; i <= m; ++i)
{
cin >> a >> b >> c1 >> c2;
e[i] = make_pair(make_pair(a, b), make_pair(c1, c2));
}
ll ans = Try(n, m);
for(int i = 1; i <= n; ++i)
edf[i].clear();
for(int i = 1; i <= m; ++i)
{
a = n - e[i].st.st + 1; b = n - e[i].st.nd + 1; c1 = e[i].nd.st; c2 = e[i].nd.nd;
e[i] = make_pair(make_pair(a, b), make_pair(c1, c2));
}
ans = min(ans, Try(n, m));
ans = min(ans, Licz(n, m));
if(ans < I)
cout << ans << "\n";
else
cout << -1 << "\n";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//int t; cin >> t;
//while(t--)
Solve();
return 0;
}
