#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
int n;
vector<multiset<pair<int, int>>> g;
void djikstra(int src, vector<long long> &sp) {
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
pq.push({sp[src] = 0, src});
vector<bool> vis(n);
while (pq.size()) {
int u = pq.top().second;
pq.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto [v, w] : g[u]) {
if (sp[u] + w < sp[v])
sp[v] = sp[u] + w, pq.push({sp[v], v});
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int m;
cin >> n >> m;
g.resize(n);
vector<long long> sp1, sp2;
vector<vector<long long>> dp(n, vector<long long> (n, INF));
vector<tuple<int, int, int, int>> edges;
for (int i = 0; i < m; i++) {
int u, v, c, d;
cin >> u >> v >> c >> d;
--u, --v;
g[u].insert({v, c});
dp[u][v] = min(dp[u][v], (long long) c);
edges.push_back({u, v, c, d});
}
for (int i = 0; i < n; i++) dp[i][i] = 0;
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
long long ans = dp[0][n - 1] + dp[n - 1][0];
for (auto [u, v, c, d] : edges) {
if (u && v && u != n - 1 && v != n - 1) {
ans = min(ans, dp[0][v] + dp[u][n - 1] + dp[n - 1][0] + c + d);
ans = min(ans, dp[0][n - 1] + dp[n - 1][v] + dp[u][0] + c + d);
} else {
g[u].erase(g[u].find({v, c}));
g[v].insert({u, c});
sp1 = sp2 = vector<long long> (n, INF);
djikstra(0, sp1), djikstra(n - 1, sp2);
ans = min(ans, sp1[n - 1] + sp2[0] + d);
g[v].erase(g[v].find({u, c}));
g[u].insert({v, c});
}
}
cout << (ans == INF ? -1 : ans) << '\n';
}
