#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
const int maxn = 205;
const int M = 5e4 + 4;
int n, m;
int eu[M], ev[M], ew[M], ed[M];
vector<pair<int, int>> g[maxn], rev_g[maxn];
long long d[2][maxn], rev[2][maxn];
long long dd[2][maxn];
int tr[maxn];
bool opt[M];
void dijkstra(int src, long long d[], bool rv) {
for (int i = 1; i <= n; ++i) {
d[i] = 1e18;
tr[i] = 0;
}
d[src] = 0;
using T = pair<long long, int>;
priority_queue<T, vector<T>, greater<T>> pq;
pq.emplace(0, src);
while (!pq.empty()) {
auto [dist, u] = pq.top();
pq.pop();
if (dist > d[u]) continue;
vector<pair<int, int>> &adj = (rv ? rev_g[u] : g[u]);
for (auto [v, id] : adj) {
if (d[v] > ew[id] + dist) {
tr[v] = id;
pq.emplace(d[v] = ew[id] + dist, v);
}
}
}
}
void invert(int id) {
int u = eu[id], v = ev[id];
for (int i = 0; i < (int)g[u].size(); ++i) {
if (g[u][i].second == id) {
swap(g[u][i], g[u][(int)g[u].size() - 1]);
g[u].pop_back();
break;
}
}
g[v].emplace_back(u, id);
swap(eu[id], ev[id]);
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v, w, d; cin >> u >> v >> w >> d;
g[u].emplace_back(v, i);
rev_g[v].emplace_back(u, i);
eu[i] = u, ev[i] = v, ew[i] = w, ed[i] = d;
}
dijkstra(1, d[0], 0);
for (int i = 1; i <= n; ++i) {
opt[tr[i]] = 1;
}
dijkstra(n, d[1], 0);
for (int i = 1; i <= n; ++i) {
opt[tr[i]] = 1;
}
dijkstra(1, rev[0], 1);
dijkstra(n, rev[1], 1);
long long res = d[0][n] + d[1][1];
for (int i = 1; i <= m; ++i) {
int u = eu[i], v = ev[i];
if (!opt[i]) {
long long x = min(d[0][n], d[0][v] + rev[1][u] + ew[i]);
long long y = min(d[1][1], d[1][v] + rev[0][u] + ew[i]);
// debug(i, x, y, ed[i]);
res = min(res, ed[i] + x + y);
} else {
invert(i);
dijkstra(1, dd[0], 0);
dijkstra(n, dd[1], 0);
// debug(i, dd[0][n], dd[1][1], ed[i]);
res = min(res, dd[0][n] + dd[1][1] + ed[i]);
invert(i);
}
}
cout << (res > 1e17 ? -1 : res);
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
