#include <bits/stdc++.h>
#include <experimental/random>
#include <random>
using namespace std;
using ll = long long;
using ld = long double;
const int INF = 1e9, MOD = 998244353;
void solve();
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int q = 1;
//cin >> q;
while (q--) {
solve();
}
}
struct e {
int v, c, d, id;
};
int n, m;
vector<vector<int>> calc(vector<vector<e>>& g, int s) {
vector<pair<int, int>> pred(n, {-1, -1});
vector<int> dp(n, INF);
dp[s] = 0;
set<pair<int, int>> dj;
dj.insert({0, s});
while (!empty(dj)) {
auto [w, u] = *dj.begin();
dj.erase(dj.begin());
for (auto [v, c, d, id] : g[u]) {
if (dp[v] > w + c) {
pred[v] = {u, id};
dj.erase({dp[v], v});
dp[v] = w + c;
dj.insert({dp[v], v});
}
}
}
vector<vector<int>> ans(n, vector<int>(m));
for (int i = 0; i < n; i++) {
int t = i;
while (pred[t].second != -1) {
ans[i][pred[t].second] = 1;
t = pred[t].first;
}
}
return ans;
}
vector<int> cost(vector<vector<e>>& g, int s) {
vector<int> dp(n, INF);
dp[s] = 0;
set<pair<int, int>> dj;
dj.insert({0, s});
while (!empty(dj)) {
auto [w, u] = *dj.begin();
dj.erase(dj.begin());
for (auto [v, c, d, id] : g[u]) {
if (dp[v] > w + c) {
dj.erase({dp[v], v});
dp[v] = w + c;
dj.insert({dp[v], v});
}
}
}
return dp;
}
void rev_ed(int u, int v, int idx, vector<vector<e>>& g) {
vector<e> x = g[u];
g[u].clear();
e hv{};
for (auto ed : x) {
if (ed.id != idx) {
g[u].push_back(ed);
} else {
hv = ed;
}
}
g[v].push_back({u, hv.c, hv.d, hv.id});
}
void del_ed(int u, int idx, vector<vector<e>>& g) {
vector<e> x = g[u];
g[u].clear();
for (auto ed : x) {
if (ed.id != idx) {
g[u].push_back(ed);
}
}
}
void solve() {
cin >> n >> m;
vector<vector<e>> g(n), rev_g(n);
vector<e> edges;
for (int i = 0; i < m; i++) {
int u, v, c, d;
cin >> u >> v >> c >> d;
u--, v--;
edges.push_back({u, v, c, d});
g[u].push_back({v, c, d, i});
rev_g[v].push_back({u, c, d, i});
}
vector<vector<int>> dp1 = calc(g, 0);
vector<vector<int>> dp2 = calc(rev_g, n - 1);
vector<vector<int>> dp3 = calc(g, n - 1);
vector<vector<int>> dp4 = calc(rev_g, 0);
vector<int> c1 = cost(g, 0);
vector<int> c2 = cost(rev_g, n - 1);
vector<int> c3 = cost(g, n - 1);
vector<int> c4 = cost(rev_g, 0);
int ans = c1[n - 1] + c3[0];
for (int i = 0; i < m; i++) {
auto [u, v, w, d] = edges[i];
rev_ed(u, v, i, g);
rev_ed(v, u, i, rev_g);
int p1 = c1[n - 1], p2 = c3[0];
if (dp1[n - 1][i]) {
p1 = cost(g, 0)[n - 1];
}
if (dp3[0][i]) {
p2 = cost(g, n - 1)[0];
}
int cnt = c1[v] + w;
if (dp1[v][i]) {
del_ed(u, i, g);
cnt = cost(g, 0)[v] + w;
g[u].push_back({v, w, d, i});
}
int cnt2 = c2[u];
if (dp2[u][i]) {
del_ed(v, i, rev_g);
cnt2 = cost(rev_g, n - 1)[u];
rev_g[v].push_back({u, w, d, i});
}
p1 = min(p1, cnt + cnt2);
cnt = c3[v] + w;
if (dp3[v][i]) {
del_ed(u, i, g);
cnt = cost(g, n - 1)[v] + w;
g[u].push_back({v, w, d, i});
}
cnt2 = c4[u];
if (dp4[u][i]) {
del_ed(v, i, rev_g);
cnt2 = cost(rev_g, 0)[u];
rev_g[v].push_back({u, w, d, i});
}
p2 = min(p2, cnt + cnt2);
ans = min(ans, p1 + p2 + d);
rev_ed(v, u, i, g);
rev_ed(u, v, i, rev_g);
}
if (ans >= INF) {
cout << -1;
return;
}
cout << ans;
}
