#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 202, M = 50005, oo = 1e12;
void mini(int &X, int Y) {
if (X > Y) X = Y;
}
int n, m;
vector<array<int, 3>> Adj[N], rAdj[N];
array<int, 4> e[M];
int d1[N], rdn[N], rd1[N], dn[N];
bool on[2][M];
void Dijkstra(int st, vector<array<int, 3>> *adj, int *d, int t) {
fill(d + 1, d + 1 + n, oo);
d[st] = 0;
priority_queue<pair<int, int>> pq;
pq.emplace(0, st);
vector<int> prv(n + 1);
while (pq.size()) {
int u, di; tie(di, u) = pq.top();
di = -di;
pq.pop();
if (d[u] != di) continue;
for (auto V: adj[u]) {
int v, w, id; tie(v, w, id) = {V[0], V[1], V[2]};
if (d[v] > di + w) {
if (t >= 0) prv[v] = id;
pq.emplace(-(d[v] = di + w), v);
}
}
}
if (t >= 0 && d[n + 1 - st] < oo) {
for (int cur = n + 1 - st; cur != st; cur = e[prv[cur]][0]) {
on[t][prv[cur]] = true;
}
// I traced one shortest path from 1 to n and n to 1
}
}
vector<int> l1, ln; vector<bool> vis;
int Dijkstra_recalc(int id) {
fill(l1.begin(), l1.end(), oo);
l1[1] = 0;
fill(vis.begin(), vis.end(), false);
for (int t = 1; t <= n; t++) {
pair<int, int> best = {oo, -1};
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
best = min(best, {l1[i], i});
}
}
if (best.second < 0) break;
int u = best.second;
vis[u] = true;
if (e[id][1] == u) {
int v = e[id][0], w = e[id][2];
mini(l1[v], l1[u] + w);
}
for (auto V: Adj[u]) {
if (V[2] == id) continue;
int v, w; tie(v, w) = {V[0], V[1]};
mini(l1[v], l1[u] + w);
}
}
fill(ln.begin(), ln.end(), oo);
ln[n] = 0;
fill(vis.begin(), vis.end(), false);
for (int t = 1; t <= n; t++) {
pair<int, int> best = {oo, -1};
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
best = min(best, {ln[i], i});
}
}
if (best.second < 0) break;
int u = best.second;
vis[u] = true;
if (e[id][1] == u) {
int v = e[id][0], w = e[id][2];
mini(ln[v], ln[u] + w);
}
for (auto V: Adj[u]) {
if (V[2] == id) continue;
int v, w; tie(v, w) = {V[0], V[1]};
mini(ln[v], ln[u] + w);
}
}
return l1[n] + ln[1];
}
void solve(void) {
cin >> n >> m;
for (int i = 1, a, b, c, d; i <= m; i++) {
cin >> a >> b >> c >> d;
Adj[a].push_back({b, c, i});
rAdj[b].push_back({a, c, i});
e[i] = {a, b, c, d};
}
Dijkstra(1, Adj, d1, 0); Dijkstra(n, rAdj, rdn, -1);
Dijkstra(n, Adj, dn, 1); Dijkstra(1, rAdj, rd1, -1);
int ans = d1[n] + dn[1];
l1.resize(n + 1); ln = l1; vis.resize(n + 1);
for (int i = 1; i <= m; i++) {
int d = e[i][3];
if (on[0][i] || on[1][i]) {
mini(ans, Dijkstra_recalc(i) + d);
// I will just use Dijkstra's algo to recalculate if it's an edge I have traced before
} else {
int u = e[i][0], v = e[i][1], c = e[i][2];
mini(ans, min(d1[v] + c + rdn[u], d1[n]) + min(dn[v] + c + rd1[u], dn[1]) + d);
}
}
if (ans >= oo) ans = -1;
cout << ans;
}
signed main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr);
int TEST = 1;
while (TEST--) solve();
return 0;
}
