#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 = 1e17+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+1, INF);
vector<bool> vis(N, false);
dist[s] = 0;
while (true) {
int u = N;
for (int i = 0; i < N; i++)
if (!vis[i] && dist[i] < dist[u])
u = i;
if (u == N) break;
for (auto [v, i] : g[typ][u]) if (dist[v] > dist[u] + w[i])
dist[v] = dist[u] + w[i], prev[v] = i;
vis[u] = true;
}
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+1, INF);
vector<bool> vis(N, false);
dist[s] = 0;
while (true) {
int u = N;
for (int i = 0; i < N; i++)
if (!vis[i] && dist[i] < dist[u])
u = i;
if (u == N) break;
for (auto [v, i] : g[0][u]) if (i != reve)
dist[v] = min(dist[v], dist[u] + w[i]);
if (b[reve] == u)
dist[a[reve]] = min(dist[a[reve]], dist[u] + w[reve]);
vis[u] = true;
}
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 lol = revw[i];
if (used1[i]) lol += getdist(0, N-1, i);
else lol += min(from1[N-1], from1[b[i]] + toN[a[i]] + w[i]);
if (usedN[i]) lol += getdist(N-1, 0, i);
else lol += min(fromN[0], fromN[b[i]] + to1[a[i]] + w[i]);
ans = min(ans, lol);
}
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();
}
