#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200, M = 50000;
const ll infL = 3e18;
bool in_s[M], in_n[M];
ll distS[N], distN[N], distAllS[N], distAllN[N], tmp[N];
int A[M], B[M], W[M], D[M], n, m;
void dijkstra(int s, vector<pair<int, int>> g[], ll dist[], bool need, bool in[], int blocked = -1) {
fill(dist, dist + n, infL);
dist[s] = 0;
int S = s;
vector<bool> was(n);
vector<int> par(n, -1);
while (s != -1) {
was[s] = true;
for (auto [to, i]: g[s]) {
if (i != blocked && dist[to] > dist[s] + W[i]) {
dist[to] = dist[s] + W[i];
par[to] = i;
}
}
int nxt = -1;
for (int i = 0; i < n; ++i) {
if (!was[i] && dist[i] != infL && (nxt == -1 || dist[nxt] > dist[i])) {
nxt = i;
}
}
s = nxt;
}
if (need) {
for (int i = 0; i < n; ++i) {
if (par[i] != -1) {
in[par[i]] = true;
}
}
}
}
vector<pair<int, int>> g[N], revg[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < m; ++i) {
cin >> A[i] >> B[i] >> W[i] >> D[i];
--A[i], --B[i];
g[A[i]].emplace_back(B[i], i);
revg[B[i]].emplace_back(A[i], i);
}
dijkstra(n - 1, g, distN, true, in_n);
dijkstra(0, g, distS, true, in_s);
dijkstra(0, revg, distAllS, false, nullptr);
dijkstra(n - 1, revg, distAllN, false, nullptr);
ll ans = infL;
ans = min(ans, distS[n - 1] + distN[0]);
for (int i = 0; i < m; ++i) {
ll valSN, valNS;
if (in_s[i]) {
dijkstra(0, g, tmp, false, nullptr, i);
valSN = tmp[n - 1];
} else {
valSN = min(distS[n - 1], distS[B[i]] + W[i] + distAllN[A[i]]);
}
if (in_n[i]) {
dijkstra(n - 1, g, tmp, false, nullptr, i);
valNS = tmp[0];
} else {
valNS = min(distN[0], distN[B[i]] + W[i] + distAllS[A[i]]);
}
ans = min(ans, D[i] + valNS + valSN);
}
cout << (ans == infL ? -1 : ans);
return 0;
}
