#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, cnt[N][N], used[N], val[N][N]; vector <int> g[N]; void dfs(int v) { used[v] = 1; for (auto to : g[v]) { if (!used[to]) dfs(to); } } void solve() { cin >> n >> m; vector <pair<int,int>> save; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { val[i][j] = inf; } } for (int i = 1; i <= m; i++) { int u, v, c, d; cin >> u >> v >> c >> d; cnt[u][v]++; val[u][v] = min(val[u][v], d); if (cnt[u][v] == 1) save.push_back(mp(u, v)); } int ok1 = 0, ok2 = 0; dfs(1); if (used[n]) ok1 = 1; for (int i = 1; i <= n; i++) used[i] = 0; dfs(n); if (used[1]) ok2 = 1; if (ok1 && ok2) { cout << 0; return; } int ans = inf; for (auto [x, y] : save) { cnt[x][y]--; g[y].push_back(x); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (cnt[i][j]) g[i].push_back(j); } } cnt[x][y]++; for (int i = 1; i <= n; i++) used[i] = 0; int ok1 = 0, ok2 = 0; dfs(1); if (used[n]) ok1 = 1; for (int i = 1; i <= n; i++) used[i] = 0; dfs(n); if (used[1]) ok2 = 1; if (ok1 && ok2) { ans = min(ans, val[x][y]); } for (int i = 1; i <= n; i++) g[i].clear(); } 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'; } }