#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; int n, m, can_to1[N], can_toN[N], can_from1[N], can_fromN[N], used[N], cnt[N][N]; vector <int> g[N]; void dfs(int v, int tp) { used[v] = 1; if (!tp) can_from1[v] = 1; else can_fromN[v] = 1; for (auto to : g[v]) { if (!used[to]) { dfs(to, tp); } } } void dfs2(int v, int tp) { used[v] = 1; if (!tp) can_to1[v] = 1; else can_toN[v] = 1; for (auto to : g[v]) { if (!used[to]) { dfs2(to, tp); } } } bool check(int v, int goal) { used[v] = 1; if (v == goal) return true; for (auto to : g[v]) { if (!used[to] && cnt[v][to] > 0) { if (check(to, goal)) return true; } } return false; } void solve() { cin >> n >> m; vector <pair<int,pair<int,int>>> save; for (int i = 1; i <= m; i++) { int u, v, c, d; cin >> u >> v >> c >> d; cnt[u][v]++; g[u].push_back(v); save.push_back(mp(d, mp(u, v))); } int ok1 = check(1, n); for (int i = 1; i <= n; i++) { used[i] = 0; } int ok2 = check(n, 1); if (ok1 && ok2) { cout << 0; return; } for (int i = 1; i <= n; i++) { used[i] = 0; } sort(save.begin(), save.end()); dfs(1, 0); for (int i = 1; i <= n; i++) { used[i] = 0; } dfs(n, 1); for (int i = 1; i <= n; i++) { used[i] = 0; g[i].clear(); } for (auto to : save) { int u = to.se.fi, v = to.se.se; g[v].push_back(u); } dfs2(1, 0); for (int i = 1; i <= n; i++) { used[i] = 0; } dfs2(n, 1); if (!ok1 && !ok2) { for (auto to : save) { int d = to.fi, u = to.se.fi, v = to.se.se; if (can_from1[v] && can_fromN[v] && can_to1[u] && can_toN[u]) { cout << d; return; } } cout << -1; return; } for (int i = 1; i <= n; i++) { g[i].clear(); } for (auto to : save) { g[to.se.fi].push_back(to.se.se); } for (int i = 0; i < Sz(save); i++) { pair <int,pair<int,int>> to = save[i]; int d = to.fi, u = to.se.fi, v = to.se.se; for (int j = 1; j <= n; j++) { used[j] = 0; } g[v].push_back(u); cnt[u][v]--; cnt[v][u]++; int Ok1 = check(1, n); for (int j = 1; j <= n; j++) { used[j] = 0; } int Ok2 = check(n, 1); g[v].pop_back(); cnt[u][v]++; cnt[v][u]--; if (Ok1 && Ok2) { cout << d; return; } } cout << -1; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int tt = 1; // cin >> tt; while (tt--) { solve(); // cout << '\n'; } }