/**
* author: wxhtzdy
* created: 07.07.2022 13:22:29
**/
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> u(m), v(m), c(m), d(m);
vector<vector<tuple<int, int, int>>> g(n);
const long long inf = 1e16;
vector<vector<long long>> f(n, vector<long long>(n, inf));
for (int i = 0; i < m; i++) {
cin >> u[i] >> v[i] >> c[i] >> d[i];
--u[i]; --v[i];
g[u[i]].emplace_back(v[i], c[i], i);
f[u[i]][v[i]] = min(f[u[i]][v[i]], (long long) c[i]);
}
for (int i = 0; i < n; i++) {
f[i][i] = 0;
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
}
}
auto ng = g;
vector<vector<int>> ids(2);
vector<vector<long long>> dist(2, vector<long long>(n));
function<void(int, int, int)> FindPath = [&](int s, int t, int id) {
fill(dist[id].begin(), dist[id].end(), inf);
set<pair<long long, int>> st;
vector<int> prv(n);
dist[id][s] = 0;
st.emplace(0, s);
while (!st.empty()) {
auto it = st.begin();
int i = it->second;
st.erase(it);
for (auto& e : ng[i]) {
int to = get<0>(e);
int w = get<1>(e);
int idx = get<2>(e);
if (dist[id][to] > dist[id][i] + w) {
if (dist[id][to] != inf) {
st.erase(st.find({dist[id][to], to}));
}
dist[id][to] = dist[id][i] + w;
prv[to] = idx;
st.emplace(dist[id][to], to);
}
}
}
ids[id].clear();
if (dist[id][t] != inf) {
while (t != s) {
ids[id].push_back(prv[t]);
t = u[prv[t]];
}
}
};
FindPath(0, n - 1, 0);
FindPath(n - 1, 0, 1);
vector<int> on(m, -1);
for (int r = 0; r < 2; r++) {
for (int i : ids[r]) {
on[i] = r;
}
}
long long ans = min(inf, f[0][n - 1] + f[n - 1][0]);
auto Solve = [&](int id) {
for (int i = 0; i < n; i++) {
ng[i].clear();
}
swap(u[id], v[id]);
for (int i = 0; i < m; i++) {
ng[u[i]].emplace_back(v[i], c[i] + (i == id ? d[i] : 0), i);
}
FindPath(0, n - 1, 0);
FindPath(n - 1, 0, 1);
swap(u[id], v[id]);
return dist[0][n - 1] + dist[1][0];
};
for (int i = 0; i < m; i++) {
if (on[i] != -1) {
ans = min(ans, Solve(i));
continue;
}
ans = min(ans, f[n - 1][0] + f[0][v[i]] + c[i] + d[i] + f[u[i]][n - 1]);
ans = min(ans, f[n - 1][v[i]] + c[i] + d[i] + f[u[i]][0] + f[0][n - 1]);
}
cout << (ans >= inf ? (long long) -1 : ans) << '\n';
return 0;
}
