#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define ld long double
#define ar array
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9+7;
const int INF = 1e15+5;
const int MXN = 205, MXM = 50005;
vector<ar<int,2>> g[2][MXN];
int a[MXM], b[MXM], w[MXM], revw[MXM], N, M;
void dijkstra(int s, int t, int typ, vector<int> &dist, vector<bool> &used) {
vector<int> prev(N, -1);
used.resize(M, false); dist.resize(N, INF);
priority_queue<ar<int,3>, vector<ar<int,3>>, greater<ar<int,3>>> pq;
pq.push({0, s, -1});
while (!pq.empty()) {
auto [d, u, e] = pq.top(); pq.pop();
if (dist[u] <= d) continue;
dist[u] = d; prev[u] = e;
for (auto [v, i] : g[typ][u]) if (dist[v] > d+w[i])
pq.push({d+w[i], v, i});
}
if (typ) return;
for (int cur = t; prev[cur] != -1; cur = a[prev[cur]])
used[prev[cur]] = true;
}
int getdist(int s, int t, int reve) {
vector<int> dist(N, INF);
priority_queue<ar<int,2>, vector<ar<int,2>>, greater<ar<int,2>>> pq;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (dist[u] <= d) continue;
dist[u] = d;
for (auto [v, i] : g[0][u]) if (dist[v] > d+w[i] && i != reve)
pq.push({d+w[i], v});
if (u == b[reve] && dist[a[reve]] > d+w[reve])
pq.push({d+w[reve], a[reve]});
}
return dist[t];
}
void solve() {
cin >> N >> M;
for (int i = 0; i < M; i++) {
cin >> a[i] >> b[i] >> w[i] >> revw[i];
g[0][--a[i]].push_back({--b[i], i});
g[1][b[i]].push_back({a[i], i});
}
vector<int> to1, toN, from1, fromN;
vector<bool> used1, usedN, tmp;
dijkstra(0, N-1, 0, from1, used1);
dijkstra(N-1, 0, 0, fromN, usedN);
dijkstra(0, N-1, 1, to1, tmp);
dijkstra(N-1, 0, 1, toN, tmp);
int ans = from1[N-1] + fromN[0];
for (int i = 0; i < M; i++) {
int tmp = revw[i];
if (used1[i]) tmp += getdist(0, N-1, i);
else tmp += min(from1[N-1], from1[b[i]] + toN[a[i]] + w[i]);
if (usedN[i]) tmp += getdist(N-1, 0, i);
else tmp += min(fromN[0], fromN[b[i]] + to1[a[i]] + w[i]);
ans = min(ans, tmp);
}
if (ans >= INF/2) cout << -1 << '\n';
else cout << ans << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t = 1; //cin >> t;
while (t--) solve();
}
