#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
const int maxn = 205;
const int M = 5e4 + 4;
int n, m;
int eu[M], ev[M], ew[M], ed[M];
vector<pair<int, int>> g[maxn], rev_g[maxn];
bool opt[M];
long long d[maxn][2][maxn][2];
map<pair<int, int>, int> mp;
void dijkstra(int src) {
memset(d, 0x3f, sizeof(d));
d[src][0][0][0] = 0;
using T = tuple<long long, int, bool, int, bool>;
priority_queue<T, vector<T>, greater<T>> pq;
pq.emplace(0, src, 0, 0, 0);
while (!pq.empty()) {
auto [dist, u, round, rv, best] = pq.top();
pq.pop();
// debug(u, round, rv, dist);
if (dist > d[u][round][rv][best]) continue;
for (auto [v, id] : g[u]) {
int nxt_round = round | (v == n);
if (rv == v) {
if (!(best and opt[id])) {
if (d[v][nxt_round][n + 1][0] > dist + ew[id]) {
d[v][nxt_round][n + 1][0] = dist + ew[id];
pq.emplace(d[v][nxt_round][n + 1][0], v, nxt_round, n + 1, 0);
}
}
} else {
int xx = (!rv ? 0 : n + 1);
if (d[v][nxt_round][xx][0] > dist + ew[id]) {
d[v][nxt_round][xx][0] = dist + ew[id];
pq.emplace(d[v][nxt_round][xx][0], v, nxt_round, xx, 0);
}
}
}
if (!rv) {
for (auto [v, id] : rev_g[u]) {
int nxt_round = round | (v == n);
if (d[v][nxt_round][u][opt[id]] > dist + ew[id] + ed[id]) {
d[v][nxt_round][u][opt[id]] = dist + ew[id] + ed[id];
pq.emplace(d[v][nxt_round][u][1], v, nxt_round, u, opt[id]);
}
}
}
}
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v, w, d; cin >> u >> v >> w >> d;
g[u].emplace_back(v, i);
rev_g[v].emplace_back(u, i);
eu[i] = u, ev[i] = v, ew[i] = w, ed[i] = d;
if (!mp.count(make_pair(u, v))) {
mp[make_pair(u, v)] = i;
} else if (ew[mp[make_pair(u, v)]] > ew[i]) {
mp[make_pair(u, v)] = i;
}
}
for (auto [u, id] : mp) {
opt[id] = 1;
}
dijkstra(1);
long long res = 1e18;
for (int i = 0; i <= n + 1; ++i) {
for (int j = 0; j < 2; ++j) {
res = min(res, d[1][1][i][j]);
}
}
cout << (res > 1e17 ? -1 : res);
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
