#include <bits/stdc++.h> #define int 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 int inf = 1e18; int n, m, used[N], comp[N]; vector <int> g[N], order; void dfs(int v) { used[v] = 1; for (auto to : g[v]) { if (!used[to]) dfs(to); } order.push_back(v); } void dfs2(int v, int ind) { comp[v] = ind; used[v] = 1; for (auto to : g[v]) { if (!used[to]) dfs2(to, ind); } } void solve() { cin >> n >> m; vector <pair<pair<int,int>,int>> edges; vector <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); edges.push_back(mp(mp(u, v), d)); save.push_back(mp(u, v)); } for (int i = 1; i <= n; i++) { if (!used[i]) { dfs(i); } } reverse(order.begin(), order.end()); for (int i = 1; i <= n; i++) { g[i].clear(); used[i] = 0; } for (auto [u, v] : save) { g[v].push_back(u); } int sz = 0; for (auto to : order) { if (!used[to]) { dfs2(to, ++sz); } } if (comp[1] == comp[n]) { cout << 0; return; } for (int i = 1; i <= n; i++) { g[i].clear(); used[i] = 0; } for (auto [u, v] : save) { if (comp[u] != comp[v]) { g[comp[u]].push_back(comp[v]); } } int s = 1, f = n; if (comp[s] > comp[f]) swap(s, f); dfs(comp[s]); if (!used[f]) { cout << -1; return; } for (int i = 1; i <= n; i++) { used[i] = 0; } dfs(comp[f]); int ans = inf; vector <int> have; for (auto to : edges) { int v = to.fi.fi, u = to.fi.se, d = to.se; if (comp[v] == comp[s] && used[comp[u]] && comp[u] != comp[f]) { ans = min(ans, d); } if (comp[v] == comp[s] && comp[u] == comp[f]) { have.push_back(d); } } sort(have.begin(), have.end()); if (Sz(have) >= 2) ans = min(ans, have[0]); 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'; } }