#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
cin.tie(0)->sync_with_stdio(0);
int n, m;
cin >> n >> m;
vector<vector<int>> elist;
elist.push_back({0, 0, 0, 0});
vector<vector<int>> floyd(n, vector<int>(n, INT_MAX));
for (int i = 0; i < n; i++) {
floyd[i][i] = 0;
}
vector<vector<pair<int, int>>> adj(n, vector<pair<int, int>>());
for (int i = 0; i < m; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
a--, b--;
elist.push_back({a, b, c, d});
floyd[a][b] = min(floyd[a][b], c);
adj[a].emplace_back(b, c);
}
for (int times = 0; times < 6; times++)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
floyd[i][j] = min(floyd[i][j], floyd[i][k] + floyd[k][j]);
}
}
}
auto dijkstra = [&](vector<int>& visited, int a, int b) {
priority_queue<pair<int, int>, vector<pair<int, int>>,
greater<pair<int, int>>>
pqpii;
pqpii.emplace(a, b);
while (!pqpii.empty()) {
pair<int, int> cur = pqpii.top();
pqpii.pop();
if (visited[cur.second] != INT_MAX) continue;
visited[cur.second] = cur.first;
for (auto a : adj[cur.second])
pqpii.emplace(a.second + cur.first, a.first);
}
};
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// cout << floyd[i][j] << " ";
// }
// cout << "\n";
// }
int minans = INT_MAX;
for (int i = 0; i <= m; i++) {
vector<int> c1(floyd[0]), c2(floyd[n - 1]);
int u = elist[i][1], v = elist[i][0], cst = elist[i][2];
c1[v] = min(c1[v], c1[u] + cst);
c2[v] = min(c2[v], c2[u] + cst);
for (int j = 0; j < n; j++) {
c1[j] = min(c1[j], c1[v] + floyd[v][j]);
c2[j] = min(c2[j], c2[v] + floyd[v][j]);
}
// cout << i << " " << c1[n - 1] << " " << c2[0] << " " << elist[i][3] <<
// "\n";
minans = min(minans, c1[n - 1] + c2[0] + elist[i][3]);
}
if (minans == INT_MAX) {
cout << "-1\n";
} else
cout << minans << "\n";
}
