#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define mp make_pair
#define Sz(x) (int)x.size()
using namespace std;
const int N = 205;
const ll inf = 1e18;
int n, m, cnt[N][N], ind[N][N], ind2[N][N];
ll dist[N][N], dist2[N][N], dp[N][N], D[N], mn[N][N], mn2[N][N];
vector <int> g[N];
ll get(int s, int f) {
for (int i = 1; i <= n; i++) {
D[i] = inf;
}
priority_queue <pair<ll,int>> st;
D[s] = 0;
st.push(mp(0, s));
while (Sz(st) > 0) {
pair <ll,int> p = st.top();
st.pop();
int v = p.se;
ll val = -p.fi;
if (D[v] < val) continue;
for (auto to : g[v]) {
if (!cnt[v][to] || dist[v][to] == inf) continue;
if (D[to] > val + dist[v][to]) {
D[to] = val + dist[v][to];
st.push(mp(-D[to], to));
}
}
}
return D[f];
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = inf;
mn[i][j] = inf;
mn2[i][j] = inf;
dist[j][j] = 0;
}
}
vector <pair<pair<int,int>,pair<int,int>>> save;
for (int i = 1; i <= m; i++) {
int u, v, c, d;
cin >> u >> v >> c >> d;
g[u].push_back(v);
cnt[u][v]++;
save.push_back(mp(mp(u, v), mp(c, d)));
if (c <= dist[u][v]) {
dist2[u][v] = dist[u][v];
dist[u][v] = c;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = dist[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int v = 1; v <= n; v++) {
for (int u = 1; u <= n; u++) {
if (dp[v][i] == inf || dp[i][u] == inf) continue;
if (dp[v][u] > dp[v][i] + dp[i][u]) {
dp[v][u] = dp[v][i] + dp[i][u];
}
}
}
}
if (dp[1][n] == inf && dp[n][1] == inf) {
ll ans = inf;
for (int i = 0; i < Sz(save); i++) {
int u = save[i].fi.fi, v = save[i].fi.se;
int c = save[i].se.fi, d = save[i].se.se;
if (dp[n][v] != inf && dp[u][1] != inf && dp[1][v] != inf && dp[u][n] != inf) {
ans = min(ans, dp[n][v] + dp[u][1] + dp[1][v] + dp[u][n] + (ll)c + (ll)d);
}
if (dp[1][v] != inf && dp[u][n] != inf && dp[n][v] != inf && dp[u][1] != inf) {
ans = min(ans, dp[1][v] + dp[u][n] + dp[n][v] + dp[u][1] + (ll)c + (ll)d);
}
}
cout << ans;
return;
}
ll ans = inf;
if (dp[1][n] != inf && dp[n][1] != inf) {
ans = dp[1][n] + dp[n][1];
}
vector <pair<ll,int>> save2, save3;
for (int i = 0; i < Sz(save); i++) {
int u = save[i].fi.fi, v = save[i].fi.se;
int c = save[i].se.fi, d = save[i].se.se;
if (dp[n][v] != inf && dp[u][1] != inf && dp[1][n] != inf) {
ll val = dp[n][v] + dp[u][1] + (ll)c + (ll)d + dp[1][n];
if (mn[u][v] > val) {
mn[u][v] = val;
ind[u][v] = i;
}
}
if (dp[1][v] != inf && dp[u][n] != inf && dp[n][1] != inf) {
ll val = dp[1][v] + dp[u][n] + (ll)c + (ll)d + dp[n][1];
if (mn2[u][v] > val) {
mn2[u][v] = val;
ind2[u][v] = i;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (mn[i][j] != inf) save2.push_back(mp(mn[i][j], ind[i][j]));
if (mn2[i][j]!= inf) save3.push_back(mp(mn2[i][j], ind2[i][j]));
}
}
sort(save2.begin(), save2.end());
sort(save3.begin(), save3.end());
for (auto to : save2) {
int pos = to.se;
int u = save[pos].fi.fi, v = save[pos].fi.se;
int c = save[pos].se.fi, d = save[pos].se.se;
ll old_uv = dist[u][v], old_vu = dist[v][u];
dist[u][v] = dist2[u][v]; dist[v][u] = min(dist[v][u], (ll)c);
cnt[u][v]--;
cnt[v][u]++;
g[v].push_back(u);
ll val = get(1, n);
cnt[u][v]++;
cnt[v][u]--;
g[v].pop_back();
dist[u][v] = old_uv; dist[v][u] = old_vu;
if (val != inf) ans = min(ans, val + dp[n][v] + dp[u][1] + (ll)c + (ll)d);
if (val == dp[1][n]) break;
}
for (auto to : save3) {
int pos = to.se;
int u = save[pos].fi.fi, v = save[pos].fi.se;
int c = save[pos].se.fi, d = save[pos].se.se;
ll old_uv = dist[u][v], old_vu = dist[v][u];
dist[u][v] = dist2[u][v]; dist[v][u] = min(dist[v][u], (ll)c);
cnt[u][v]--;
cnt[v][u]++;
g[v].push_back(u);
ll val = get(n, 1);
cnt[u][v]++;
cnt[v][u]--;
g[v].pop_back();
dist[u][v] = old_uv; dist[v][u] = old_vu;
if (val != inf) ans = min(ans, val + dp[1][v] + dp[u][n] + (ll)c + (ll)d);
if (val == dp[n][1]) break;
}
if (ans == inf) cout << -1;
else cout << ans;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int tt = 1;
// cin >> tt;
while (tt--) {
solve();
// cout << '\n';
}
}
