#include <bits/stdc++.h>
#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))
constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl
#define ll long long
#define pb push_back
#define int ll
using namespace std;
constexpr int inf = 1e18 + 7;
int n, m;
vector<array<int, 4>> edges;
vector<pair<int, int>> whichEdge;
vector<vector<pair<int, int>>> g, gR;
vector<vector<vector<int>>> dist; // from 1, from N, to 1, to N
vector<vector<vector<int>>> minPref, minSuf;
void calcDistWithout(int X, int S, int which, bool rev) {
vector<bool> vis(n + 1, 0);
rep(i, 1, n + 1) dist[which][X][i] = inf;
dist[which][X][S] = 0;
int squirt = (int)sqrt(n);
vector<pair<int, int>> sqAr((n + 1) / squirt + 1, {inf, inf});
sqAr[S / squirt] = {0, S};
while(true) {
pair<int, int> minDist = {inf, inf};
repIn(i, sqAr) minDist = min(minDist, i);
auto [ds, v] = minDist;
if(ds == inf) break;
vis[v] = true;
sqAr[v / squirt] = {inf, inf};
int mysq = v / squirt;
rep(i, mysq * squirt, min(mysq * squirt + squirt, n + 1)) if(!vis[i]) sqAr[mysq] = min(sqAr[mysq], {dist[which][X][i], i});
if(v == X) continue;
repIn2(u, d, (rev ? gR : g)[v]) if(!vis[u]) dist[which][X][u] = min(dist[which][X][u], ds + d), sqAr[u / squirt] = min(sqAr[u / squirt], {ds + d, u});
}
}
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
edges.resize(m);
whichEdge.resize(m);
g.resize(n + 1);gR.resize(n + 1);
dist.resize(4, vector<vector<int>>(n + 1, vector<int>(n + 1)));
minPref.resize(4, vector<vector<int>>(n + 1));
minSuf.resize(4, vector<vector<int>>(n + 1));
rep(i, 0, m) {
int v, u, c1, c2;
cin >> v >> u >> c1 >> c2;
edges[i] = {v, u, c1, c2};
whichEdge[i] = {g[v].size(), gR[u].size()};
g[v].pb({u, c1});
gR[u].pb({v, c1});
}
rep(i, 1, n + 1) calcDistWithout(i, 1, 0, 0);
rep(i, 1, n + 1) calcDistWithout(i, n, 1, 0);
rep(i, 1, n + 1) calcDistWithout(i, 1, 2, 1);
rep(i, 1, n + 1) calcDistWithout(i, n, 3, 1);
DEBUG {
DC << "Dist from 1: " << eol;
rep(i, 1, n + 1) {
DC << " without " << i << ": " << eol;
rep(j, 1, n + 1) DC << " (" << j << "): " << dist[0][i][j] << eol;
}
DC << "Dist from N: " << eol;
rep(i, 1, n + 1) {
DC << " without " << i << ": " << eol;
rep(j, 1, n + 1) DC << " (" << j << "): " << dist[1][i][j] << eol;
}
DC << "Dist to 1: " << eol;
rep(i, 1, n + 1) {
DC << " without " << i << ": " << eol;
rep(j, 1, n + 1) DC << " (" << j << "): " << dist[2][i][j] << eol;
}
DC << "Dist to N: " << eol;
rep(i, 1, n + 1) {
DC << " without " << i << ": " << eol;
rep(j, 1, n + 1) DC << " (" << j << "): " << dist[3][i][j] << eol;
}
}
rep(which, 0, 4) rep(v, 1, n + 1) {
minPref[which][v].resize(g[v].size());
int mp = inf;
int i = 0;
repIn2(u, c, g[v]) {
mp = min(mp, c + dist[which][v][u]);
minPref[which][v][i++] = mp;
}
}
rep(which, 0, 4) rep(v, 1, n + 1) {
minSuf[which][v].resize(g[v].size());
int mp = inf;
int i = (int)g[v].size() - 1;
ranges::reverse(g[v]);
repIn2(u, c, g[v]) {
mp = min(mp, c + dist[which][v][u]);
minSuf[which][v][i--] = mp;
}
ranges::reverse(g[v]);
}
int ans = min(inf, dist[0][n][n] + dist[1][1][1]);
DC << "if we reverse nothing ans = " << ans << eol;
int i = 0;
for(auto [v, u, c1, c2] : edges) {
auto [ii, ir] = whichEdge[i];
int toN = min(dist[0][v][n], dist[0][v][v] + min((ii ? minPref[3][v][ii - 1] : inf), (ii < (int)g[v].size() - 1 ? minSuf[3][v][ii + 1] : inf)));
toN = min(toN, dist[0][v][u] + c1 + dist[3][u][v]);
int fromN = min(dist[1][v][1], dist[1][v][v] + min((ii ? minPref[2][v][ii - 1] : inf), (ii < (int)g[v].size() - 1 ? minSuf[2][v][ii + 1] : inf)));
fromN = min(fromN, dist[1][v][u] + c1 + dist[2][u][v]);
DC << "if we reverse edge " << i << " ans = " << toN + fromN + c2 << eol;
ans = min(ans, toN + fromN + c2);
i++;
}
cout << (ans == inf ? -1 : ans) << '\n';
}
