#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]; 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]) { 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; 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; } int s = 1, f = n; if (ok2) swap(s, f); 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++) { g[j].clear(); used[j] = 0; } g[v].push_back(u); for (int j = 0; j < Sz(save); j++) { if (j == i) continue; g[save[j].se.fi].push_back(save[j].se.se); } int Ok1 = check(s, f); for (int j = 1; j <= n; j++) { used[j] = 0; } int Ok2 = check(f, s); 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'; } }