#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';
}
}
