#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 1e5 + 7, INF = 1e18 + 7;
struct Edge {
int u, v, c, d;
} e[N];
struct Ed {
int v, c, i;
};
int n, m;
int dist1[N], par1[N], par_ed1[N], sec1[N], best1[N];
int distn[N], parn[N], par_edn[N], secn[N], bestn[N];
int tmp[N];
int dist1_rev[N], sec1_rev[N], best1_rev[N];;
int distn_rev[N], secn_rev[N], bestn_rev[N];
vector <Ed> g[N], gr[N];
int get1n(int u, int v) {
return dist1[u] + distn_rev[v];
}
int getn1(int u, int v) {
return distn[u] + dist1_rev[v];
}
int get1n(int i) {
return get1n(e[i].u, e[i].v) + e[i].c;
}
int getn1(int i) {
return getn1(e[i].u, e[i].v) + e[i].c;
}
void dj(int S, int *dist, vector <Ed> g[N], int par[N], int par_ed[N], int sec[N], int best[N]) {
for (int i = 0; i < N; ++i) {
dist[i] = INF;
best[i] = -1;
sec[i] = INF;
}
set <ii> ms;
dist[S] = 0;
ms.insert(mp(0, S));
while (ms.size()) {
int u = ms.begin()->s;
ms.erase(ms.begin());
for (auto e : g[u]) {
if (dist[u] + e.c < dist[e.v]) {
ms.erase(mp(dist[e.v], e.v));
sec[e.v] = dist[e.v];
dist[e.v] = dist[u] + e.c;
par[e.v] = u;
par_ed[e.v] = e.i;
best[e.v] = e.i;
ms.insert(mp(dist[e.v], e.v));
}
else {
sec[e.v] = min(sec[e.v], dist[u] + e.c);
}
}
}
}
int from1(int u, int ban) {
if (ban != best1[u])
return dist1[u];
else
return sec1[u];
}
int ton(int u, int ban) {
if (ban != bestn_rev[u])
return distn_rev[u];
else
return secn_rev[u];
}
int fromn(int u, int ban) {
if (ban != bestn[u])
return distn[u];
else
return secn[u];
}
int to1(int u, int ban) {
if (ban != best1_rev[u])
return dist1_rev[u];
else
return sec1_rev[u];
}
int dist1n_del[N], distn1_del[N];
vector <int> tree[N], add[N], del[N];
bool used[N];
const int LG = 20;
int to[N][LG], tin[N], tout[N], timer = 0;
void dfs1(int u, int p) {
to[u][0] = p;
for (int i = 1; i < LG; ++i)
to[u][i] = to[to[u][i - 1]][i - 1];
tin[u] = timer++;
for (int v : tree[u])
dfs1(v, u);
tout[u] = timer++;
}
bool anc(int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
bool vert(int u, int v) {
return anc(u, v) || anc(v, u);
}
int lca(int u, int v) {
if (anc(u, v))
return u;
for (int i = LG - 1; i >= 0; --i)
if (!anc(to[u][i], v))
u = to[u][i];
return to[u][0];
}
bool inp1[N], inpn[N];
int getup(int u, int v) {
if (anc(u, v))
return u;
else
return v;
}
int mmin(int u, int v) {
if (anc(u, v))
return v;
else
return u;
}
void upd(int &a, int b) {
if (a == -1)
a = b;
else
a = mmin(a, b);
}
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
#else
ios_base::sync_with_stdio(0); cin.tie(0);
#endif
cin >> n >> m;
for (int i = 0; i < m; ++i) {
cin >> e[i].u >> e[i].v >> e[i].c >> e[i].d;
g[e[i].u].app({e[i].v, e[i].c, i});
gr[e[i].v].app({e[i].u, e[i].c, i});
}
dj(1, dist1, g, par1, par_ed1, sec1, best1);
dj(n, distn, g, parn, par_edn, secn, bestn);
dj(1, dist1_rev, gr, tmp, tmp, sec1_rev, best1_rev);
dj(n, distn_rev, gr, tmp, tmp, secn_rev, bestn_rev);
for (int i = 2; i <= n; ++i)
if (par1[i]) {
tree[par1[i]].app(i);
used[par_ed1[i]] = 1;
}
dfs1(1, 1);
/*
for (int i = 1; i <= n; ++i)
cout << par1[i] << ' ';
cout << '\n';
*/
for (int i = 0; i < m; ++i) {
if (!used[i]) {
int l = lca(e[i].u, e[i].v);
l = lca(l, n);
int x = get1n(i);
add[lca(e[i].u, n)].app(x);
del[l].app(x);
add[lca(e[i].v, n)].app(x);
del[l].app(x);
}
}
if (!par1[n]) {
for (int i = 0; i < N; ++i)
dist1n_del[i] = INF;
}
else {
for (int i = 0; i < N; ++i)
dist1n_del[i] = dist1[n];
int u = n;
multiset <int> ms = {INF};
while (u != 1) {
//cout << "up " << u << '\n';
for (int e : add[u]) {
ms.insert(e);
//cout << "insert " << e << '\n';
}
for (int e : del[u]) {
ms.erase(ms.find(e));
//cout << "erase " << e << '\n';
}
dist1n_del[par_ed1[u]] = *ms.begin();
inp1[par_ed1[u]] = 1;
u = to[u][0];
}
}
for (int i = 0; i < N; ++i) {
tree[i].clear();
add[i].clear();
del[i].clear();
}
memset(used, 0, sizeof used);
for (int i = 1; i < n; ++i)
if (parn[i]) {
tree[parn[i]].app(i);
used[par_edn[i]] = 1;
}
dfs1(n, n);
for (int i = 0; i < m; ++i) {
if (!used[i]) {
int l = lca(e[i].u, e[i].v);
l = lca(l, 1);
int x = getn1(i);
add[lca(e[i].u, 1)].app(x);
del[l].app(x);
add[lca(e[i].v, 1)].app(x);
del[l].app(x);
}
}
if (!parn[1]) {
for (int i = 0; i < N; ++i)
distn1_del[i] = INF;
}
else {
for (int i = 0; i < N; ++i)
distn1_del[i] = distn[1];
int u = 1;
multiset <int> ms = {INF};
while (u != n) {
for (int e : add[u])
ms.insert(e);
for (int e : del[u])
ms.erase(ms.find(e));
distn1_del[par_edn[u]] = *ms.begin();
inpn[par_edn[u]] = 1;
u = to[u][0];
}
}
#ifdef HOME
for (int i = 0; i < m; ++i)
cout << dist1n_del[i] << ' ';
cout << '\n';
for (int i = 0; i < m; ++i)
cout << distn1_del[i] << ' ';
cout << '\n';
#endif
int ans = dist1[n] + distn[1];
for (int i = 0; i < m; ++i) {
int d1n = INF, dn1 = INF;
if (!inp1[i])
d1n = from1(e[i].v, i) + ton(e[i].u, i) + e[i].c;
if (!inpn[i])
dn1 = fromn(e[i].v, i) + to1(e[i].u, i) + e[i].c;
d1n = min(d1n, dist1n_del[i]);
dn1 = min(dn1, distn1_del[i]);
ans = min(ans, d1n + dn1 + e[i].d);
//cout << i << ' ' << d1n << ' ' << dn1 << ' ' << e[i].d << '\n';
}
if (ans > 1e12)
cout << "-1\n";
else
cout << ans << '\n';
}
