/// @author Camillus
#include <bits/stdc++.h>
#define int long long
using ll = long long;
using namespace std;
int from[50'000];
int to[50'000];
int cost[50'000];
int change[50'000];
static constexpr int INF = 1e17;
int n, m;
vector<pair<int, int>> g[200];
int d_from[200];
int d_to[200];
vector<int> shuffled;
void dist_from_all(int s) {
for (int u = 0; u < n; u++) {
g[u].resize(0);
}
for (int i : shuffled) {
g[to[i]].emplace_back(from[i], cost[i]);
}
auto d = d_to;
for (int i = 0; i < n; i++) {
d[i] = INF;
}
d[s] = 0;
set<pair<int, int>> Q;
Q.emplace(d[s], s);
while (!Q.empty()) {
int u = Q.begin()->second;
Q.erase(Q.begin());
for (auto [v, c] : g[u]) {
if (d[v] > d[u] + c) {
Q.erase(pair(d[v], v));
d[v] = d[u] + c;
Q.emplace(d[v], v);
}
}
}
}
void dist_to_all(int s) {
for (int u = 0; u < n; u++) {
g[u].resize(0);
}
for (int i : shuffled) {
g[from[i]].emplace_back(to[i], cost[i]);
}
auto d = d_from;
for (int i = 0; i < n; i++) {
d[i] = INF;
}
d[s] = 0;
set<pair<int, int>> Q;
Q.emplace(d[s], s);
while (!Q.empty()) {
int u = Q.begin()->second;
Q.erase(Q.begin());
for (auto [v, c] : g[u]) {
if (d[v] > d[u] + c) {
Q.erase(pair(d[v], v));
d[v] = d[u] + c;
Q.emplace(d[v], v);
}
}
}
}
int get_cost() {
int result = 0;
dist_to_all(0);
dist_from_all(0);
return min(INF, d_from[n - 1] + d_to[n - 1]);
}
random_device rd;
mt19937_64 rnd(rd());
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
shuffled.resize(m);
iota(shuffled.begin(), shuffled.end(), 0);
shuffle(shuffled.begin(), shuffled.end(), rnd);
for (int i = 0; i < m; i++) {
int u, v, c, d;
cin >> u >> v >> c >> d;
u--, v--;
from[i] = u;
to[i] = v;
cost[i] = c;
change[i] = d;
}
auto group1 = [&]() -> bool {
return m <= 1000;
};
auto group2 = [&]() -> bool {
if (m % 2 == 1) {
return false;
}
for (int i = 0; i < m; i += 2) {
bool condition = from[i] == from[i + 1] && to[i] == to[i + 1] && cost[i] == cost[i + 1];
if (!condition) {
return false;
}
}
return true;
};
auto group3 = [&]() -> bool {
for (int i = 0; i < m; i++) {
if (cost[i] != 0) {
return false;
}
}
return true;
};
vector<vector<int>> d(n, vector<int>(n, INF));
vector<int> good;
for (int i = 0; i < m; i++) {
d[from[i]][to[i]] = min(d[from[i]][to[i]], cost[i]);
}
for (int u = 0; u < n; u++) {
d[u][u] = 0;
}
for (int k = 0; k < n; k++) {
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
d[u][v] = min(d[u][v], d[u][k] + d[k][v]);
}
}
}
vector<int> best1(m);
iota(best1.begin(), best1.end(), 0);
sort(best1.begin(), best1.end(), [&](int i, int j) -> bool {
auto val = [&](int x) -> int {
return d[0][to[x]] + cost[x] + change[x] + d[from[x]][n - 1];
};
return val(i) < val(j);
});
best1.resize(min(best1.size(), (size_t)100));
vector<int> best2(m);
iota(best2.begin(), best2.end(), 0);
sort(best2.begin(), best2.end(), [&](int i, int j) -> bool {
auto val = [&](int x) -> int {
return d[n - 1][to[x]] + cost[x] + change[x] + d[from[x]][0];
};
return val(i) < val(j);
});
best2.resize(min(best2.size(), (size_t)100));
vector<int> best;
for (int i : best1) {
best.push_back(i);
}
for (int i : best2) {
best.push_back(i);
}
sort(best.begin(), best.end());
best.erase(unique(best.begin(), best.end()), best.end());
int initial = get_cost();
int ans = initial;
for (int i : best) {
swap(from[i], to[i]);
ans = min(ans, get_cost() + change[i]);
swap(from[i], to[i]);
}
cout << (ans == INF ? -1 : ans) << '\n';
return 0;
}
