#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]; } } } } 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'; } }