#include <bits/stdc++.h>
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;
const int inf = 1e9 + 7;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
// file("A") else file("task");
int n, m;
cin >> n >> m;
vector<vector<int>> dist(n, vector<int>(n, inf));
for(int i = 0; i < n; ++i) dist[i][i] = 0;
vector<array<int, 4>> ed(m);
vector<vector<pair<int, int>>> g(n);
for(int i = 0; i < m; ++i) {
int u, v, c, d;
cin >> u >> v >> c >> d;
--u, --v;
ed[i] = {u, v, c, d};
dist[u][v] = min(dist[u][v], c);
g[u].emplace_back(v, i);
}
for(int k = 0; k < n; ++k) {
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
long long ans = dist[0][n - 1] + dist[n - 1][0];
auto dij = [&](int s, int e, int v) {
vector<int> d(n, inf), used(n);
priority_queue<pair<int, int>> pq;
pq.emplace(0, s);
d[s] = 0;
while (!pq.empty()) {
int x = pq.top().second;
pq.pop();
if (x == e) break;
if (used[x]++) continue;
for (auto i : g[x]) {
int u = i.first, z = i.second;
if (z == v) continue;
if (d[u] > d[x] + ed[z][2]) {
d[u] = d[x] + ed[z][2];
pq.emplace(-d[u], u);
}
}
if (x == ed[v][1]) {
if (d[ed[v][0]] > d[x] + ed[v][2]) {
d[ed[v][0]] = d[x] + ed[v][2];
pq.emplace(-d[ed[v][0]], ed[v][0]);
}
}
}
return d[e];
};
for(int i = 0; i < m; ++i) {
int u = ed[i][0], v = ed[i][1], c = ed[i][2], d = ed[i][3];
long long a = min(dist[0][n - 1], dist[0][v] + dist[u][n - 1] + c);
long long b = min(dist[n - 1][0], dist[n - 1][v] + dist[u][0] + c);
if (a + b + d < ans) {
long long x = dij(0, n - 1, i);
long long y = dij(n - 1, 0, i);
ans = min(ans, x + y + d);
}
}
if(ans >= inf) ans = -1;
cout << ans << '\n';
return 0;
}
