#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, dist1[N][N], dist2[N][N]; int dp[2][N][N]; void solve() { cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dist1[i][j] = dist2[i][j] = inf; dp[0][i][j] = dp[1][i][j] = inf; } } for (int i = 1; i <= m; i++) { int u, v, c, d; cin >> u >> v >> c >> d; dist1[u][v] = min(dist1[u][v], c); dist2[v][u] = min(dist2[v][u], c + d); } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dp[0][i][j] = dist1[i][j]; dp[1][i][j] = dist2[i][j]; } } for (int i = 1; i <= n; i++) { for (int v = 1; v <= n; v++) { for (int u = 1; u <= n; u++) { if (i == v || v == u || i == u) continue; dp[0][v][u] = min(dp[0][v][u], dp[0][v][i] + dp[0][i][u]); dp[1][v][u] = min(dp[1][v][u], dp[0][v][i] + dp[1][i][u]); dp[1][v][u] = min(dp[1][v][u], dp[1][v][i] + dp[0][i][u]); } } } int ans = inf; ans = min(ans, dp[0][1][n] + dp[0][n][1]); ans = min(ans, dp[1][1][n] + dp[0][n][1]); ans = min(ans, dp[0][1][n] + dp[1][n][1]); 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'; } }