//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;
constexpr ll INF64 = 1'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;
random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());
template<typename T>
bool assign_max(T& a, T b) {
if (b > a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool assign_min(T& a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
T square(T a) {
return a * a;
}
template<>
struct std::hash<pair<ll, ll>> {
ll operator() (pair<ll, ll> p) const {
return ((__int128)p.first * MOD + p.second) % INF64;
}
};
pair<vector<ll>, vector<ll>> get_dist(ll v, vector<tuple<ll, ll, ll, ll>>& arr, ll n) {
vector<vector<ll>> to(n, vector<ll>(n, INF64));
for (auto[a, b, c, d] : arr) {
assign_min(to[a][b], c);
}
vector<ll> dist(n, INF64);
vector<ll> p(n, -1);
dist[v] = 0;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q;
q.push(make_pair(0ll, v));
while (!q.empty()) {
auto[d, x] = q.top();
q.pop();
if (d != dist[x]) {
continue;
}
for (ll i = 0; i < n; i++) {
if (assign_min(dist[i], d + to[x][i])) {
p[i] = x;
q.push(make_pair(dist[i], i));
}
}
}
return make_pair(dist, p);
}
vector<ll> get_way(ll v, vector<ll>& dist, vector<ll>& p, vector<vector<ll>>& rarr, vector<tuple<ll, ll, ll, ll>>& arr) {
ll now = v;
ll nd = dist[v];
vector<ll> ans;
if (p[now] == -1) {
return ans;
}
while (p[now] != -1) {
for (auto i : rarr[now]) {
if (nd == get<2>(arr[i]) + dist[get<0>(arr[i])] && get<0>(arr[i]) == p[now]) {
ans.push_back(i);
nd -= get<2>(arr[i]);
now = get<0>(arr[i]);
break;
}
}
}
reverse(ans.begin(), ans.end());
return ans;
}
void solve() {
ll n, m;
cin >> n >> m;
vector<tuple<ll, ll, ll, ll>> arr(m);
for (auto&[a, b, c, d] : arr) {
cin >> a >> b >> c >> d;
a--;
b--;
}
vector<vector<ll>> dists(n), ps(n);
for (ll i = 0; i < n; i++) {
auto[d, p] = get_dist(i, arr, n);
dists[i] = d;
ps[i] = p;
}
vector<vector<ll>> rarr(n);
for (ll i = 0; i < m; i++) {
rarr[get<1>(arr[i])].push_back(i);
}
vector<ll> w0n = get_way(n - 1, dists[0], ps[0], rarr, arr), wn0 = get_way(0, dists[n - 1], ps[n - 1], rarr, arr);
ll ans = dists[0][n - 1] + dists[n - 1][0];
vector<ll> d0r(m, -1), dnr(m, -1);
for (auto i : w0n) {
swap(get<0>(arr[i]), get<1>(arr[i]));
d0r[i] = get_dist(0, arr, n).first[n - 1];
swap(get<0>(arr[i]), get<1>(arr[i]));
}
for (ll i = 0; i < m; i++) {
if (d0r[i] == -1) {
d0r[i] = min(dists[0][n - 1], dists[0][get<1>(arr[i])] + get<2>(arr[i]) + dists[get<0>(arr[i])][n - 1]);
}
}
for (auto i : wn0) {
swap(get<0>(arr[i]), get<1>(arr[i]));
dnr[i] = get_dist(n - 1, arr, n).first[0];
swap(get<0>(arr[i]), get<1>(arr[i]));
}
for (ll i = 0; i < m; i++) {
if (dnr[i] == -1) {
dnr[i] = min(dists[n - 1][0], dists[n - 1][get<1>(arr[i])] + get<2>(arr[i]) + dists[get<0>(arr[i])][0]);
}
}
for (ll i = 0; i < m; i++) {
assign_min(ans, d0r[i] + dnr[i] + get<3>(arr[i]));
}
cout << (ans >= INF64 ? -1 : ans) << '\n';
}
int main() {
if (IS_FILE) {
freopen("", "r", stdin);
freopen("", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t = 1;
if (IS_TEST_CASES) {
cin >> t;
}
for (ll i = 0; i < t; i++) {
solve();
}
}
